The Path Set Packing Problem

Chenyang Xu; Guochuan Zhang

doi:10.1007/978-3-319-94776-1_26

The Path Set Packing Problem

Chenyang Xu
, Guochuan Zhang^*

^*Corresponding author for this work

Zhejiang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

In this paper, we study a variant of set packing, in which a set P of paths in a graph(Formula Presented) is given, the goal is to find a maximum number of edge-disjoint paths of P. We show that the problem is NP-hard even if each path in P contains at most three edges, while it is hard to approximate within (Formula Presented) for the general case unless (Formula Presented)x. In the positive aspect, a parameterized algorithm relying on the maximum degree and the tree-width of G is derived. For tree networks, we present a polynomial time optimal algorithm.

Original language	English
Title of host publication	Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
Editors	Daming Zhu, Lusheng Wang
Publisher	Springer Verlag
Pages	305-315
Number of pages	11
ISBN (Print)	9783319947754
DOIs	https://doi.org/10.1007/978-3-319-94776-1_26
State	Published - 2018
Externally published	Yes
Event	24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China Duration: 2 Jul 2018 → 4 Jul 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10976 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Country/Territory	China
City	Qing Dao
Period	2/07/18 → 4/07/18

Access to Document

10.1007/978-3-319-94776-1_26

Cite this

Xu, C., & Zhang, G. (2018). The Path Set Packing Problem. In D. Zhu, & L. Wang (Eds.), Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings (pp. 305-315). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10976 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-94776-1_26

@inproceedings{cbe47a1ea4bb4a95a726ad5a15aab39d,

title = "The Path Set Packing Problem",

abstract = "In this paper, we study a variant of set packing, in which a set P of paths in a graph(Formula Presented) is given, the goal is to find a maximum number of edge-disjoint paths of P. We show that the problem is NP-hard even if each path in P contains at most three edges, while it is hard to approximate within (Formula Presented) for the general case unless (Formula Presented)x. In the positive aspect, a parameterized algorithm relying on the maximum degree and the tree-width of G is derived. For tree networks, we present a polynomial time optimal algorithm.",

author = "Chenyang Xu and Guochuan Zhang",

note = "Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 24th International Conference on Computing and Combinatorics Conference, COCOON 2018 ; Conference date: 02-07-2018 Through 04-07-2018",

year = "2018",

doi = "10.1007/978-3-319-94776-1\_26",

language = "英语",

isbn = "9783319947754",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "305--315",

editor = "Daming Zhu and Lusheng Wang",

booktitle = "Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings",

address = "德国",

}

Xu, C & Zhang, G 2018, The Path Set Packing Problem. in D Zhu & L Wang (eds), Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10976 LNCS, Springer Verlag, pp. 305-315, 24th International Conference on Computing and Combinatorics Conference, COCOON 2018, Qing Dao, China, 2/07/18. https://doi.org/10.1007/978-3-319-94776-1_26

The Path Set Packing Problem. / Xu, Chenyang; Zhang, Guochuan.
Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. ed. / Daming Zhu; Lusheng Wang. Springer Verlag, 2018. p. 305-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10976 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The Path Set Packing Problem

AU - Xu, Chenyang

AU - Zhang, Guochuan

PY - 2018

Y1 - 2018

N2 - In this paper, we study a variant of set packing, in which a set P of paths in a graph(Formula Presented) is given, the goal is to find a maximum number of edge-disjoint paths of P. We show that the problem is NP-hard even if each path in P contains at most three edges, while it is hard to approximate within (Formula Presented) for the general case unless (Formula Presented)x. In the positive aspect, a parameterized algorithm relying on the maximum degree and the tree-width of G is derived. For tree networks, we present a polynomial time optimal algorithm.

AB - In this paper, we study a variant of set packing, in which a set P of paths in a graph(Formula Presented) is given, the goal is to find a maximum number of edge-disjoint paths of P. We show that the problem is NP-hard even if each path in P contains at most three edges, while it is hard to approximate within (Formula Presented) for the general case unless (Formula Presented)x. In the positive aspect, a parameterized algorithm relying on the maximum degree and the tree-width of G is derived. For tree networks, we present a polynomial time optimal algorithm.

UR - https://www.scopus.com/pages/publications/85049698331

U2 - 10.1007/978-3-319-94776-1_26

DO - 10.1007/978-3-319-94776-1_26

M3 - 会议稿件

AN - SCOPUS:85049698331

SN - 9783319947754

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

SP - 305

EP - 315

BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings

A2 - Zhu, Daming

A2 - Wang, Lusheng

PB - Springer Verlag

T2 - 24th International Conference on Computing and Combinatorics Conference, COCOON 2018

Y2 - 2 July 2018 through 4 July 2018

ER -

The Path Set Packing Problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this