Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Nonplanar Vertex Deletion: Maximum Degree Thresholds For Np/max Snp-hardness And A Frac(3, 4)-approximation For Finding Maximum Planar Induced Subgraphs
Author: Faria L.
Herrera de Figueiredo C.M.
Gravier S.
Mendonca C.F.X.
Stolfi J.
Abstract: The non planar vertex deletion v d (G), of a graph G is the smallest positive integer k, such that the removal of k vertices from G produces a planar graph. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a positive integer k, to decide whether v d (G) ≤ k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a positive integer k satisfy v d (G) ≤ k. We prove that to compute v d (G) is Max SNP-hard when restricted to a cubic input G. We exhibit a polynomial frac(3, 4)-approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph. © 2004.
Rights: fechado
Identifier DOI: 10.1016/j.endm.2004.06.019
Date Issue: 2004
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-34247380748.pdf195.33 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.