Conexão de terminais com limitação de roteadores: complexidade e relação com fluxos e caminhos disjuntos - de Melo, Alexsander Andrade; Figueiredo, Celina Miraglia Herrera de; Souza, Uéverton dos Santos (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2018: Anais do XXXI Concurso de Teses e Dissertações, 2018)
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 ∈ {0, 1}, 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.