| Título: |
Um algorítmo melhorado para encontrar FAS para grafos planares An improvement for an algorithm for finding a minimum feedback arc set for planar graphs |
| Autores: |
Mendonça Neto, Candido Ferreira Xavier de; USP Eades, Peter; UNIVERSITY NEWCASLTE |
| Fecha: | 1999-05-14 |
| Publicador: | Acta Scientiarum. Techonology |
| Fuente: |
 |
| Tipo: |
|
| Tema: |
1.03.00.00-7 Ciência da Computação FAZ; núcleos; cortes de coberturas orientadas 1.03.00.00-7 Ciência da Computação |
| Descripción: |
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. Given a directed graph G, a covering is a subset B of arcs which meets all directed cuts of G. Equivalently, the contraction of the elements of B makes G strongly connected. An O(n5) primal-dual algorithm is presented by Frank (1981) for finding a minimum covering of a directed graph. For a planar graph, the dual problem is to find a minimum set of arcs whose removal makes G acyclic. The dual problem may be solved with Frank's algorithm. Further, some improvements that may be used to make such algorithm faster in practical cases are prescuted. |
| Idioma: | Inglés |