Algorithms for finding disjoint path covers in unit interval graphs

详细信息    查看全文

• 作者：Jung-Heum Park^a ; ^{j.h.park@catholic.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Joonsoo Choi^b ; ^{jschoi@kookmin.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Hyeong-Seok Lim^c ; ^{hslim@chonnam.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Disjoint path ; Path cover ; Path partition ; Proper interval graph ; Graph algorithm
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 May 2016
• 年：2016
• 卷：205
• 期：Complete
• 页码：132-149
• 全文大小：655 K

文摘

A many-to-many k$k$-disjoint path cover   (k$k$-DPC for short) of a graph G$G$ joining the pairwise disjoint vertex sets S$S$ and ed2298a81a7979d3c0d71dd78" title="Click to view the MathML source">T$T$, each of size k$k$, is a collection of k$k$ vertex-disjoint paths between S$S$ and ed2298a81a7979d3c0d71dd78" title="Click to view the MathML source">T$T$, which altogether cover every vertex of G$G$. This is classified as paired  , if each vertex of S$S$ must be joined to a specific vertex of ed2298a81a7979d3c0d71dd78" title="Click to view the MathML source">T$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$S$ and ed2298a81a7979d3c0d71dd78" title="Click to view the MathML source">T$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$k$-DPC problem on a unit interval graph is polynomially solvable for any fixed k$k$.