Kernels for packing and covering problems

Jianer Chen, Henning Fernau, Peter Shaw, Jingxin Wang, Zhibiao Yang

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    13 Downloads (Pure)

    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 languageEnglish
    Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management
    EditorsJack Snoeyink, Pinyan Lu, Kaile Su, Lusheng Wang
    Place of PublicationOnline
    PublisherSpringer
    Pages199-211
    Number of pages13
    Volume7285
    ISBN (Print)978-3-642-29699-4
    DOIs
    Publication statusPublished - 2012
    EventJoint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012) - Beijing China, Beijing, China
    Duration: 14 May 201216 May 2012
    Conference number: 2012

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume7285
    ISSN (Print)0302-9743

    Conference

    ConferenceJoint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012)
    Abbreviated titleFAW
    CountryChina
    CityBeijing
    Period14/05/1216/05/12

    Fingerprint Dive into the research topics of 'Kernels for packing and covering problems'. Together they form a unique fingerprint.

  • Cite this

    Chen, J., Fernau, H., Shaw, P., Wang, J., & Yang, Z. (2012). Kernels for packing and covering problems. In J. Snoeyink, P. Lu, K. Su, & L. Wang (Eds.), Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Vol. 7285, pp. 199-211). (Lecture Notes in Computer Science ; Vol. 7285). Springer. https://doi.org/10.1007/978-3-642-29700-7_19