• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
Documento
Autor
Nome completo
Renzo Gonzalo Gómez Diaz
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2019
Orientador
Banca examinadora
Wakabayashi, Yoshiko (Presidente)
Fernandes, Cristina Gomes
Lee, Orlando
Lintzmayer, Carla Negri
Santos, Vinicius Fernandes dos
Título em inglês
Covering graphs by nontrivial paths
Palavras-chave em inglês
Approximation
Bounded treewidth
Covering by nontrivial paths
Integer linear formulation
Max path cover
Min path cover
Weighted path cover
[1,2]-factor
Resumo em inglês
In this thesis our aim is to study problems concerning path covers of graphs. Let G be a graph and let P be a set of pairwise vertex-disjoint paths in G. We say that P is a path cover if every vertex of G belongs to a path in P. In the minimum path cover problem, one wishes to find a path cover of minimum cardinality. In this problem, known to be NP-hard, the set P may contain trivial (single-vertex) paths. We study the problem of finding a path cover composed only of nontrivial paths. First, we consider the corresponding existence problem, and show how to reduce it to a matching problem. From this reduction, we derive a characterization that allows us to find, in polynomial time, a certificate for both the YES-answer and the NO-answer. When trivial paths are forbidden, for the feasible instances, one may consider either minimizing or maximizing the number of paths in the cover. We show that the minimization problem on feasible instances is computationally equivalent to the minimum path cover problem: their optimum values coincide and they have the same approximation threshold. Moreover, we propose integer linear formulations for these problems and present some experimental results. For the maximization problem, we show that it can be solved in polynomial time. Finally, we also consider a weighted version of the path cover problem, in which we seek for a path cover with minimum or maximum total weight (the number of paths does not matter), and we show that while the first is polynomial, the second is NP-hard. Furthermore, for the maximization case, we show a constant-factor approximation algorithm. We also show that, when the input graph has bounded treewidth, both problems can be solved in linear time. To conclude, we present an integer linear formulation for the case of minimum total weight, and study the polytope obtained when the integrality constraint is relaxed. We show that there are graphs for which this polytope has fractional vertices, and we exhibit some classes of inequalities that are valid for the integral polytope and separate these vertices.
Título em português
Cobertura de grafos por caminhos não-triviais
Palavras-chave em português
Aproximação
Cobertura com pesos
Cobertura máxima
Cobertura mínima
Cobertura por caminhos não-triviais
Formulação linear inteira
Largura arbórea limitada
[1,2]-fator
Resumo em português
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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2019-11-08
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.