Abstract
We show how the notion of combinatorial duality, related to the well-known notion of duality from linear programming, may be used for translating kernel results obtained for packing problems into kernel results for covering problems. We exemplify this approach by having a closer look at the problems of packing a graph with vertex-disjoint trees with r edges. We also improve on the best known kernel size for packing graphs with trees containing two edges, which has been well studied.
Original language | English |
---|---|
Title of host publication | Frontiers in Algorithmics and Algorithmic Aspects in Information and Management |
Editors | Jack Snoeyink, Pinyan Lu, Kaile Su, Lusheng Wang |
Place of Publication | Online |
Publisher | Springer |
Pages | 199-211 |
Number of pages | 13 |
Volume | 7285 |
ISBN (Print) | 978-3-642-29699-4 |
DOIs | |
Publication status | Published - 2012 |
Event | Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012) - Beijing China, Beijing, China Duration: 14 May 2012 → 16 May 2012 Conference number: 2012 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 7285 |
ISSN (Print) | 0302-9743 |
Conference
Conference | Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012) |
---|---|
Abbreviated title | FAW |
Country/Territory | China |
City | Beijing |
Period | 14/05/12 → 16/05/12 |