Conexão de Terminais com Limitação de Roteadores: Complexidade e Relação com Fluxos e Caminhos Disjuntos
Autores
|
6330 |
2872,257,2871
|
|
|
6331 |
2872,257,2871
|
|
|
6332 |
2872,257,2871
|
Informações:
Publicações do PESC
Uma árvore de conexão de um grafo G para um subconjunto não vazio W contido em V(G) é um subgrafo T de G tal que T é uma árvore, W está contido 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 l e r; G admite uma árvore de conexão para W que contenha no máximo l elos e no máximo r roteadores?". O TCP foi provado ser NP-completo mesmo quando ou l ou r é limitado por uma constante; por outro lado, o problema foi provado ser solucionável em tempo polinomial se l 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 l é limitado por uma constante e ser solucionável em tempo polinomial se l 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 pertence a {0,1} e provamos resultados parciais para quando r é maior ou igual a 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.
A connection tree of a graph G for a non-empty subset W contained in V(G) is a tree subgraph T of G such that W is contained in 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 l and r; does G admit a connection tree for W such that it has at most l linkers and at most r routers?". The TCP was proved to be NP-complete even when either l or r is bounded by a constant; conversely, the problem was proved to be polynomial-time solvable if l 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 l is bounded by a constant and be polynomial-time solvable if l 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 belongs to? {0,1} and we prove partial results for the case in which r is greater than or equal to??? 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.