Algorithms for finding disjoint path covers in unit interval graphs

作者：Park Jung Heum; Choi Joonsoo; Lim Hyeong Seok^*

来源：Discrete Applied Mathematics, 2016, 205: 132-149.

DOI：10.1016/j.dam.2015.12.002

• Disjoint path
• Path cover
• Path partition
• Proper interval graph
• Graph algorithm

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.

• 出版日期2016-5-31