An improvement for an algorithm for finding a minimum feedback arc set for planar graphs

Authors

  • Candido Ferreira Xavier de Mendonça Neto USP Author
  • Peter Eades UNIVERSITY NEWCASLTE Author

DOI:

https://doi.org/10.4025/actascitechnol.v21i0.3081

Keywords:

FAZ, núcleos, cortes de coberturas orientadas

Abstract

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.

Downloads

Download data is not yet available.

Author Biography

  • Candido Ferreira Xavier de Mendonça Neto, USP
    Possui graduação em Matemática pela Universidade Estadual de Campinas (1981), mestrado em Ciência da Computação pela Universidade Estadual de Campinas (1987) e doutorado em Computer Science - University of Queensland (1994), livre-docência em Combinatória e Grafos pela Universidade Estadual de Campinas (2000). Atualmente é professor associado da Escola de Artes, Ciências e Humanidades da Universidade de São Paulo. Tem experiência na área de Ciência da Computação, com ênfase em Desenho de Grafos, Análise de Algoritmos e Complexidade de Computação, atuando principalmente nos seguintes temas: Desenho de Grafos, Resolução de Conflitos na Extração de Recursos Naturais, Suporte Computacional para Crescimento Sustentável, Planarização de Grafos e Invariantes de Não-planaridade Currí­culo Lattes

Downloads

Published

2008-05-14

Issue

Vol. 21 (1999)

Section

Informatics

License

DECLARATION OF ORIGINALITY AND COPYRIGHTS

I Declare that current article is original and has not been submitted for publication, in part or in whole, to any other national or international journal. 

The copyrights belong exclusively to the authors. Published content is licensed under Creative Commons Attribution 4.0 (CC BY 4.0) guidelines, which allows sharing (copy and distribution of the material in any medium or format) and adaptation (remix, transform, and build upon the material) for any purpose, even commercially, under the terms of attribution.

Read this link for further information on how to use CC BY 4.0 properly.

 

How to Cite

An improvement for an algorithm for finding a minimum feedback arc set for planar graphs. (2008). Acta Scientiarum. Technology, 21, 841-845. https://doi.org/10.4025/actascitechnol.v21i0.3081

Similar Articles

1-10 of 1185

You may also start an advanced similarity search for this article.