Covering graphs by nontrivial paths (2019)
- Authors:
- Autor USP: DIAZ, RENZO GONZALO GÓMEZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: CIENCIA DA COMPUTACAO
- Keywords: Bounded treewidth; Cobertura com pesos; Cobertura máxima; Cobertura mínima; Formulação linear inteira; Integer linear formulation; Largura arbórea limitada; Max path cover; Min path cover; Weighted path cover; [1,2]-fator
- Agências de fomento:
- Language: Inglês
- Abstract: Nesta tese nosso foco é o estudo de problemas sobre cobertura por caminhos em grafos. Sejam G um grafo e P um conjunto de caminhos disjuntos nos vértices de G. Dizemos que P é uma cobertura por caminhos} se todo vértice de G pertence a algum caminho de P. No problema da cobertura mínima por caminhos, desejamos encontrar uma cobertura por caminhos cuja cardinalidade seja mínima. Neste problema, sabido ser NP-difícil, o conjunto P pode conter caminhos triviais. Estudamos a variante do problema onde desejamos encontrar uma cobertura por caminhos não-triviais. Inicialmente, consideramos o problema relacionado à existência de tal cobertura, e mostramos como reduzi-lo a um problema de emparelhamento. Por meio desta redução mostramos uma caracterização que nos permite encontrar, em tempo polinomial, um certificado tanto para o caso positivo quanto para o caso negativo. Uma vez que proibimos caminhos triviais, para as instâncias viáveis, podemos consider minimizar ou maximizar o número de caminhos da cobertura. Mostramos que o problema de minimização é computacionalmente equivalente ao problema da cobertura mínima por caminhos: seus valores ótimos coincidem e têm o mesmo limiar de aproximabilidade. Além disso, propomos formulações lineares inteiras para estes problemas e apresentamos alguns resultados experimentais. No caso do problema de maximização, mostramos que este pode ser resolvido em tempo polinomial.Finalmente, também consideramos a versão com pesos do problema da cobertura por caminhos, no qual buscamos uma cobertura de peso total máximo ou mínimo (sem considerar o número de caminhos), e mostramos que o primeiro pode ser resolvido em tempo polinomial, enquanto o segundo é NP-difícil. Além disso, para o caso de maximização, mostramos um algoritmo de aproximação de fator constante. Por outro lado, quando consideramos grafos com largura arbórea limitada, mostramos que ambos os problemas podem ser resolvidos em tempo linear. Concluímos mostrando uma formulação linear inteira para o caso de cobertura de peso mínimo, e estudamos o politopo que se obtém ao relaxar a restrição de integralidade. Mostramos que existem grafos para os quais este politopo tem vértices fracionários, e exibimos algumas classes de inequações válidas (para o poliedro inteiro) que separam tais vértices
- Imprenta:
- Data da defesa: 02.09.2019
-
ABNT
GÓMEZ DIAZ, Renzo Gonzalo. Covering graphs by nontrivial paths. 2019. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2019. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08112019-153707/. Acesso em: 22 jan. 2026. -
APA
Gómez Diaz, R. G. (2019). Covering graphs by nontrivial paths (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08112019-153707/ -
NLM
Gómez Diaz RG. Covering graphs by nontrivial paths [Internet]. 2019 ;[citado 2026 jan. 22 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08112019-153707/ -
Vancouver
Gómez Diaz RG. Covering graphs by nontrivial paths [Internet]. 2019 ;[citado 2026 jan. 22 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08112019-153707/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
