@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 = "德国",
}