TY - GEN
T1 - Connected feedback vertex set in planar graphs
AU - Grigoriev, Alexander
AU - Sitters, René
PY - 2010
Y1 - 2010
N2 - We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.
AB - We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.
UR - http://www.scopus.com/inward/record.url?scp=72249108235&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72249108235&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-11409-0_13
DO - 10.1007/978-3-642-11409-0_13
M3 - Conference contribution
AN - SCOPUS:72249108235
SN - 3642114083
SN - 9783642114083
VL - 5911 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 143
EP - 153
BT - Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers
T2 - 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
Y2 - 24 June 2009 through 26 June 2009
ER -