O Grafo de Interseção de Caminhos em Estrelas Longas

Jayme L Szwacfiter^{1,2,3} Chao-Ping I. Yan^{1} Universidade Federal do Rio de Janeiro

RESUMO

Uma estrela longa é uma grafo formado por um conjunto de caminhos induzidos, que se interceptam em exatamente um vértice. Apresentamos uma caracterização do grafo de interseção de caminhos em uma estrela longa. Esta caracterização conduz a um algoritmo de tempo polinomial para reconhecer grafos desta classe. No caso do reconhecimento ser positivo, o algoritmo, adicionalmente, contrói a estrela correspondente.

———————————

1 Instituto de Matemática 2 COPPE - Programa de Engenharia de Sistemas e Computação 3 Núcleo de Computação Eletrônica