Um algorítmo melhorado para encontrar FAS para grafos planares
DOI:
https://doi.org/10.4025/actascitechnol.v21i0.3081Palavras-chave:
FAZ, núcleos, cortes de coberturas orientadasResumo
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
Downloads
Publicado
Como Citar
Edição
Seção
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.
