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

  • Alexsander Andrade de Melo
  • Uéverton dos Santos Souza

Resumo


Investigamos a complexidade do PROBLEMA DE CONEXÃO DE TERMINAIS (TCP), um problema de projeto de redes diretamente relacionado a diversos problemas clássicos. Particularmente, analisamos a versão estrita do TCP, denotada por S-TCP, quando o parâmetro r é limitado por uma constante. Provamos que, para r 2 f0; 1g, o S-TCP é solucionável em tempo polinomial, o que contrasta com a complexidade do TCP, que é sabidamente NP-completo para todo r 0. Ademais, com o intuito de compreender melhor os casos em que r 2, estudamos algumas variantes do S-TCP e o relacionamos com problemas de fluxo em redes e de caminhos disjuntos. Provamos a NP-completude de um problema de fluxo integral, fechando uma questão em aberto por quarenta anos. Por fim, estabelecemos uma dicotomia poly vs. NP-c para o TCP e para o S-TCP com respeito ao grau máximo do grafo entrada e ao parâmetro.

Publicado
26/07/2018
DE MELO, Alexsander Andrade; SOUZA, Uéverton dos Santos. Conexão de terminais com limitação de roteadores: complexidade e relação com fluxos e caminhos disjuntos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 31. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2763-8820. DOI: https://doi.org/10.5753/ctd.2018.3651.