Kernels for packing and covering problems

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

doi:10.1007/978-3-642-29700-7_19

Kernels for packing and covering problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

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 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	https://doi.org/10.1007/978-3-642-29700-7_19
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	China
City	Beijing
Period	14/05/12 → 16/05/12

Access to Document

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

Link to publication in Scopus

Cite this

@inproceedings{11dad7f8c7684f169b6a6dd105221e43,

title = "Kernels for packing and covering problems",

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.",

keywords = "Covering problems, Kernel size, Packing problems, Algorithms, Forestry, Trees (mathematics), Algorithms, Forestry, Problem Solving",

author = "Jianer Chen and Henning Fernau and Peter Shaw and Jingxin Wang and Zhibiao Yang",

year = "2012",

doi = "10.1007/978-3-642-29700-7_19",

language = "English",

isbn = "978-3-642-29699-4",

volume = "7285",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "199--211",

editor = "Jack Snoeyink and Pinyan Lu and Kaile Su and Lusheng Wang",

booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management",

address = "Switzerland",

note = "Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012), FAW ; Conference date: 14-05-2012 Through 16-05-2012",

}

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, Lecture Notes in Computer Science , vol. 7285, Springer, Online, pp. 199-211, Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012), Beijing, China, 14/05/12. https://doi.org/10.1007/978-3-642-29700-7_19

Kernels for packing and covering problems. / Chen, Jianer; Fernau, Henning; Shaw, Peter; Wang, Jingxin; Yang, Zhibiao.

Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. ed. / Jack Snoeyink; Pinyan Lu; Kaile Su; Lusheng Wang. Vol. 7285 Online : Springer, 2012. p. 199-211 (Lecture Notes in Computer Science ; Vol. 7285).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Kernels for packing and covering problems

AU - Chen, Jianer

AU - Fernau, Henning

AU - Shaw, Peter

AU - Wang, Jingxin

AU - Yang, Zhibiao

N1 - Conference code: 2012

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Covering problems

KW - Kernel size

KW - Packing problems, Algorithms

KW - Forestry, Trees (mathematics), Algorithms

KW - Forestry

KW - Problem Solving

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-84861214673&doi=10.1007%2f978-3-642-29700-7_19&partnerID=40&md5=42c85edd0a8ec9715620f5f6f2110506

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

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

M3 - Conference Paper published in Proceedings

SN - 978-3-642-29699-4

VL - 7285

T3 - Lecture Notes in Computer Science

SP - 199

EP - 211

BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management

A2 - Snoeyink, Jack

A2 - Lu, Pinyan

A2 - Su, Kaile

A2 - Wang, Lusheng

PB - Springer

CY - Online

T2 - Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2012)

Y2 - 14 May 2012 through 16 May 2012

ER -

Kernels for packing and covering problems

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this