Data/hora: 01/06/2024 02:31:17

Biblioteca(s): | Embrapa Agricultura Digital.
Data corrente: | 17/06/1996
Data da última atualização: | 14/03/2011
Autoria: | CARMO, R. J. da S.; WAKABAYASHI, Y.
Afiliação: | RENATO JOSÉ DA SILVA CARMO, UFPR; YOSHIKO WAKABAYASHI, IME/USP.
Título: | The maximum planar subgraph problem.
Ano de publicação: | 1995
Fonte/Imprenta: | In: SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE, 22.; CONFERÊNCIA LATINO-AMERICANA, 21., 1995, Canela. Anais... Porto Alegre: UFRGS, Instituto de Informática, 1995.
Volume: | v.2
Páginas: | p. 1425-1433.
Idioma: | Inglês
Conteúdo: | This work is concerned with the problem of finding a maximum weight planar subgraph of a given graph. An original and simplified proof of the NP-completeness of the problem is presented. We describe a new implementation of the well-known Hopcroft/Tarjan's planarity testing algorithm, designed to be useful as a subroutine to be applied several times on non-necessarily biconnected graphs. Based on this approach, we propose a non-naive implementation of the greedy scheme whose running time is significantly lower than the ones achieved by the implementation found in the literature. Experimental results of this implementation are shown and analyzed. The absolute performance ratio of the greedy approach to the maximum planar subgraph problem is determined. Other heuristics found in the literature are presented under a unified frame and comparatively analyzed. Part of the work presents a fully detailed description of the planarity testing algorithm, with the aim of providing a didactic presentation to algorithms based on Hopcroft/Tarjan's approach. In doing so we introduce the idea of hierarchies as a useful conceptual tool to describe formally depth-first-search properties of a graph.
Palavras-Chave: | Algoritmo de Hopcroft/Tarjan; Subgrafo planar.
Thesaurus Nal: | Algorithms.
Categoria do assunto: | X Pesquisa, Tecnologia e Engenharia
Registro original: | Embrapa Agricultura Digital (CNPTIA)
Exemplares: | CNPTIA - (3305-1) - ADD - PL - PP - 004 - SEM - 1995.00014 - DIS