Show simple item record

Covering a Graph with a Constrained Forest

dc.contributor.authorBazgan, Cristina
dc.contributor.authorCouëtoux, Basile
HAL ID: 5077
dc.contributor.authorTuza, Zsolt
dc.date.accessioned2010-06-29T17:59:32Z
dc.date.available2010-06-29T17:59:32Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4495
dc.language.isoenen
dc.subjectgraphs
dc.subject.ddc005en
dc.titleCovering a Graph with a Constrained Forest
dc.typeCommunication / Conférence
dc.description.abstractenGiven 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.citationpages892-901
dc.relation.ispartoftitleAlgorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings
dc.relation.ispartofeditorYingfei Dong, Ding-Zhu Du, Oscar Ibarra
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2009
dc.relation.ispartofurl10.1007/978-3-642-10631-6
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-642-10630-9
dc.relation.confcountryUNITED STATES
dc.identifier.doi10.1007/978-3-642-10631-6_90
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-02-07T16:23:03Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record