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

v. 21 (1999)

Seção

Informática

Licença

DECLARAÇíO DE ORIGINALIDADE E DIREITOS AUTORAIS

Declaro que o presente artigo é original, não tendo sido submetido í  publicação em qualquer outro periódico nacional ou internacional, quer seja em parte ou em sua totalidade.

Os direitos autorais pertencem exclusivamente aos autores. Os direitos de licenciamento utilizados pelo periódico é a licença Creative Commons Attribution 4.0 (CC BY 4.0): são permitidos o compartilhamento (cópia e distribuição do material em qualqer meio ou formato) e adaptação (remix, transformação e criação de material a partir do conteúdo assim licenciado para quaisquer fins, inclusive comerciais. 

Recomenda-se a leitura desse link para maiores informações sobre o tema: fornecimento de créditos e referências de forma correta, entre outros detalhes cruciais para uso adequado do material licenciado.