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

Autores

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

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

Os dados de download ainda não estão disponíveis.

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

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.

 

Como Citar

Um algorí­tmo melhorado para encontrar FAS para grafos planares. (2008). Acta Scientiarum. Technology, 21, 841-845. https://doi.org/10.4025/actascitechnol.v21i0.3081

Artigos Semelhantes

1-10 de 1185

Você também pode iniciar uma pesquisa avançada por similaridade para este artigo.