Back to Search
Start Over
Algorithms for finding disjoint path covers in unit interval graphs.
- Source :
-
Discrete Applied Mathematics . May2016, Vol. 205, p132-149. 18p. - Publication Year :
- 2016
-
Abstract
- 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 . [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*SET theory
*LINEAR systems
*GRAPH theory
*PROBLEM solving
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 205
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 114051949
- Full Text :
- https://doi.org/10.1016/j.dam.2015.12.002