Um algorítmo melhorado para encontrar FAS para grafos planares

Candido Ferreira Xavier de Mendonça Neto, Peter Eades

Resumo


Dado um grafo orientado G, uma cobertura é um subconjunto B de arestas que interceptam todos os cortes de G. De maneira equivalente, a contração das arestas de B tornam o grafo G fortemente conexo. Um algoritmo primal-dual de complexidade O(n5) é apresentado por Frank (1981), este algoritmo encontra uma cobertura mínima do grafo orientado. No caso de um grafo planar, o problema dual será encontrar um conjunto mínimo de arestas cuja remoção torna G acíclico. Neste trabalho será mostrado como utilizar o algoritmo de Frank para resolver o problema dual. Será também apresentado uma melhoria que torna o algoritmo de Frank mais eficiente em casos práticos.

Palavras-chave


FAZ; núcleos; cortes de coberturas orientadas

Texto completo:

PDF (baixado


DOI: http://dx.doi.org/10.4025/actascitechnol.v21i0.3081





ISSN 1806-2563 (impresso) e ISSN 1807-8664 (on-line) e-mail: actatech@uem.br

  

Resultado de imagem para CC BY