期刊
DISCRETE APPLIED MATHEMATICS
卷 205, 期 -, 页码 132-149出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2015.12.002
关键词
Disjoint path; Path cover; Path partition; Proper interval graph; Graph algorithm
资金
- National Research Foundation of Korea (NRF) - Ministry of Education, Science and Technology [2015R1D1A1A09056849, 2013R1A1A2012890]
- National Research Foundation of Korea [2015R1D1A1A09056849, 2013R1A1A2012890] Funding Source: Korea Institute of Science & Technology Information (KISTI), National Science & Technology Information Service (NTIS)
A many-to-many k-disjoint path cover (k-DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T, each of size k, is a collection of k vertex-disjoint paths between S and T, which altogether cover every vertex of G. This is classified as paired, if each vertex of S must be joined to a specific vertex of T, or unpaired, if there is no such constraint. In this paper, we develop a linear-time algorithm for the UNPAIRED DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the ONE-TO-ONE DPC and the ONE-TO-MANY DPC problems are reduced in linear time. Additionally, we show that the PAIRED k-DPC problem on a unit interval graph is polynomially solvable for any fixed k. (C) 2016 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据