Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/11422/8166
Especie: Dissertação
Título : Conexão de terminais com limitação de roteadores :complexidade e relação com fluxos e caminhos disjuntos
Autor(es)/Inventor(es): Melo, Alexsander Andrade de
Tutor: Figueiredo, Celina Miraglia Herrera de
Tutor : Souza, Uéverton dos Santos
Resumen: Uma árvore de conexão de um grafo G para um subconjunto não vazio W ⊆ V (G) é um subgrafo T de G tal que T é uma árvore, W ⊆ V (T) e todas as folhas de T pertencem a W. Os vértices em W são chamados de terminais, os vértices em V (T) \ W com grau exatamente 2 em T são chamados de elos e os vértices em V (T) \ W com grau ao menos 3 em T são chamados de roteadores. Em 2012, Dourado et al. propuseram o Problema de conexão de terminais (TCP), o qual consiste na seguinte questão: “dado um grafo conexo G, um conjunto de terminais W e dois inteiros não negativos ` e r; G admite uma árvore de conexão para W que contenha no máximo ` elos e no máximo r roteadores? ”. O TCP foi provado ser NP-completo mesmo quando ou ` ou r é limitado por uma constante; por outro lado, o problema foi provado ser solucionável em tempo polinomial se ` e r são ambos limitados por constantes. Posteriormente, em 2014, Dourado et al. propuseram a variante estrita do TCP na qual exige-se adicionalmente que todos os terminais sejam folhas de T, denotada por S-TCP. De igual modo ao TCP, o S-TCP foi provado ser NP-completo se ` é limitado por uma constante e ser solucionável em tempo polinomial se ` e r são ambos limitados por constantes; contudo, o caso em que apenas r é limitado por uma constante não havia sido considerado até então. Assim, estudamos o S-TCP restrito ao caso em que r é limitado por uma constante. Mais especificamente, propomos um algoritmo de tempo polinomial para o S-TCP quando r ∈ {0, 1} e provamos resultados parciais para quando r ≥ 2, exibindo relações com problemas de fluxo em redes e caminhos disjuntos. Ademais, determinamos a complexidade de algumas variantes do S-TCP. Por fim, estudamos o S-TCP e o TCP quando o grau máximo do grafo G é limitado.
Resumen: A connection tree of a graph G for a non-empty subset W ⊆ V (G) is a tree subgraph of G such that W ⊆ V (T) and every leaf of T belongs to W. The vertices in W are called terminals, the vertices in V (T) \ W with degree 2 in T are called linkers and the vertices in V (T) \ W with degree at least 3 in T are called routers. In 2012, Dourado et al. proposed the Terminal connection problem (TCP), which consists in the following question: “given a connected graph G, a terminal set W and two non-negative integers ` and r; does G admit a connection tree for W such that it has at most ` linkers and at most r routers? ”. The TCP was proved to be NP-complete even when either ` or r is bounded by a constant; conversely, the problem was proved to be polynomial-time solvable if ` and r are both bounded by constants. Later, in 2014, Dourado et al. proposed the strict variant of the TCP which further requires that every terminal must be a leaf of T, and it is denoted by S-TCP. As the TCP, the S-TCP was proved to be NP-complete if ` is bounded by a constant and be polynomial-time solvable if ` and r are both bounded by constants; however, the case in which just r is bounded by a constant was not considered. Thus, we study in this dissertation the S-TCP restricted to the case in which r is bounded by a constant. More specifically, we provide a polynomial-time algorithm for the S-TCP when r ∈ {0, 1} and we prove partial results for the case r ≥ 2, exposing relations with network flows and disjoint paths. Moreover, we determine the complexity of some variants of the S-TCP. Lastly, we study the S-TCP and the TCP when the maximum degree of the graph G is bounded.
Materia: Engenharia de Sistemas e Computação
Conexões de terminais
Caminhos disjuntos
Materia CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Programa: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Unidade de producción: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Editor: Universidade Federal do Rio de Janeiro
Fecha de publicación: feb-2017
País de edición : Brasil
Idioma de publicación: por
Tipo de acceso : Acesso Aberto
Aparece en las colecciones: Engenharia de Sistemas e Computação

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
878290.pdf2.2 MBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.