Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/10163
Type: Tese
Title: Complexity and algorithms related to two classes of graph problems
Author(s)/Inventor(s): Lima, Carlos Vinícius Gomes Costa
Advisor: Szwarcfiter, Jayme Luiz
Co-advisor: Dourado, Mitre Costa
Co-advisor: Souza, Uéverton dos Santos
Abstract: Esta tese aborda problemas associados a conversões em grafos e de edição pela remoção de um emparelhamento. Estudamos processos f-reversíveis, que são aqueles associados a um valor de limiar para cada vértice e cuja dinâmica depende da quantidade de vizinhos com estado contrário para cada vértice. Estabelecemos um limite superior justo para o tamanho do período e transiente, caracterizamos todas as árvores que alcançam o transiente máximo em processos 2-reversíveis e mostramos que determinar o tamanho de um conjunto conversor mínimo é NP-difícil. Mostramos que o modelo AND-OR define uma convexidade sobre grafos. Mostramos resultados de NP-completude e algoritmos eficientes para certos parâmetros de convexidade para esta nova, assim como algoritmos aproximativos. Introduzimos o conceito de processos de limiar generalizados, onde mostramos resultados de NP-completude e algoritmos eficientes para ambas as versões não relaxada e relaxada. Estudamos o problema de decidir se um dado grafo admite uma remoção de um emparelhamento de modo a remover todos os ciclos. Mostramos que este problema é NP-difícil mesmo para grafos subcúbicos, mas admite solução eficiente para várias classes de grafos. Estudamos o problema de decidir se um dado grafo admite uma remoção de um emparelhamento de modo a remover todos os ciclos ímpares. Mostramos que este problema é NP-difícil mesmo para grafos planares com grau limitado, mas admite solução eficiente para algumas classes de grafos. Mostramos também resultados parametrizados.
Abstract: This thesis addresses the problems associated with conversions on graphs and editing by removing a matching. We study the f-reversible processes, which are those associated with a threshold value for each vertex, and whose dynamics depends on the number of neighbors with different state for each vertex. We set a tight upper bound for the period and transient lengths, characterize all trees that reach the maximum transient length for 2-reversible processes, and we show that determining the size of a minimum conversion set is NP-hard. We show that the AND-OR model defines a convexity on graphs. We show results of NP-completeness and efficient algorithms for certain convexity parameters for this new one, as well as approximate algorithms. We introduce the concept of generalized threshold processes, where the results are NP-completeness and efficient algorithms for both non relaxed and relaxed versions. We study the problem of deciding whether a given graph admits a removal of a matching in order to destroy all cycles. We show that this problem is NP-hard even for subcubic graphs, but admits efficient solution for several graph classes. We study the problem of deciding whether a given graph admits a removal of a matching in order to destroy all odd cycles. We show that this problem is NP-hard even for planar graphs with bounded degree, but admits efficient solution for some graph classes. We also show parameterized results.
Keywords: Engenharia de Sistemas e Computação
Processos reversíveis
Processos de limiar
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Apr-2017
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
878071.pdf3,9 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.