Conexão de terminais com limitação de roteadores: complexidade e relação com fluxos e caminhos disjuntos

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.

Grantor dc:publisher

Universidade Federal do Rio de Janeiro

Year dc:date.issued

2017

Author dc:creator

• Melo, Alexsander Andrade de

Advisor dc:contributor.advisor

• Figueiredo, Celina Miraglia Herrera de

• Conexões de terminais
• Caminhos disjuntos

Statement dc:rights

• Acesso Aberto

Language dc:language

por

Handle dc:identifier.uri

http://hdl.handle.net/11422/8166

OAI identifier oai:identifier

oai:pantheon.ufrj.br:11422/8166