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

Autores

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

DOI:

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

Palavras-chave:

FAZ, núcleos, cortes de coberturas orientadas

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.

Downloads

Não há dados estatísticos.

Biografia do Autor

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

Publicado

2008-05-14

Como Citar

Mendonça Neto, C. F. X. de, & Eades, P. (2008). Um algorí­tmo melhorado para encontrar FAS para grafos planares. Acta Scientiarum. Technology, 21, 841–845. https://doi.org/10.4025/actascitechnol.v21i0.3081

Edição

Seção

Informática

 

0.8
2019CiteScore
 
 
36th percentile
Powered by  Scopus

 

 

0.8
2019CiteScore
 
 
36th percentile
Powered by  Scopus