Kernels for Packing and Covering Problems Conference Paper

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. 2012 Springer-Verlag.

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., Fernau, H., Shaw, P., Wang, J., & Yang, Z.

citation count

• 16

complete list of authors

• Chen, Jianer||Fernau, Henning||Shaw, Peter||Wang, Jianxin||Yang, Zhibiao

publication date

• May 2012

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Computer Science  Journal

keywords

• 46 Information And Computing Sciences

Digital Object Identifier (DOI)

• 10.1007/978-3-642-29700-7_19

International Standard Book Number (ISBN) 13

• 9783642296994

start page

• 199

end page

• 211

volume

• 7285

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-3-642-29700-7_19