Um algorí­tmo melhorado para encontrar FAS para grafos planares

Candido Ferreira Xavier de Mendonça Neto; Peter Eades

doi:10.4025/actascitechnol.v21i0.3081

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

Authors

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

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(n⁵) 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

PDF (Português (Brasil))

Published

2008-05-14

How to Cite

Mendonça Neto, C. F. X. de, & Eades, P. (2008). An improvement for an algorithm for finding a minimum feedback arc set for planar graphs. Acta Scientiarum. Technology, 21, 841–845. https://doi.org/10.4025/actascitechnol.v21i0.3081

Download Citation

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.

0.8

2019CiteScore

36th percentile