dc.contributor.author Bazgan, Cristina dc.contributor.author Couëtoux, Basile dc.contributor.author Tuza, Zsolt dc.date.accessioned 2010-06-29T17:59:32Z dc.date.available 2010-06-29T17:59:32Z dc.date.issued 2009 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/4495 dc.language.iso en en dc.subject graphs dc.subject.ddc 005 en dc.title Covering a Graph with a Constrained Forest dc.type Communication / Conférence dc.description.abstracten Given an undirected graph on n vertices with weights on its edges, Min WCF(p) consists of computing a covering forest of minimum weight such that each of its tree components contains at least p vertices. It has been proved that Min WCF(p) is NP-hard for any p ≥ 4 (Imielinska et al., 1993) but $(2-\frac{1}{n})$-approximable (Goemans and Williamson, 1995). While Min WCF(2) is polynomial-time solvable, already the unweighted version of Min WCF(3) is NP-hard even on planar bipartite graphs of maximum degree 3. We prove here that for any p ≥ 4, the unweighted version is NP-hard, even for planar bipartite graphs of maximum degree 3; moreover, the unweighted version for any p ≥ 3 has no ptas for bipartite graphs of maximum degree 3. The latter theorem is the first-ever APX-hardness result on this problem. On the other hand, we show that Min WCF(p) is polynomial-time solvable on graphs with bounded treewidth, and for any p bounded by $O(\frac{\log n}{\log\log n})$ it has a ptas on planar graphs. dc.identifier.citationpages 892-901 dc.relation.ispartoftitle Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings dc.relation.ispartofeditor Yingfei Dong, Ding-Zhu Du, Oscar Ibarra dc.relation.ispartofpublname Springer dc.relation.ispartofpublcity Berlin Heidelberg dc.relation.ispartofdate 2009 dc.relation.ispartofurl 10.1007/978-3-642-10631-6 dc.description.sponsorshipprivate oui en dc.subject.ddclabel Programmation, logiciels, organisation des données en dc.relation.ispartofisbn 978-3-642-10630-9 dc.relation.confcountry UNITED STATES dc.identifier.doi 10.1007/978-3-642-10631-6_90 dc.description.ssrncandidate non dc.description.halcandidate oui dc.description.readership recherche dc.description.audience International dc.date.updated 2017-02-07T16:23:03Z
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.