Golovach, P.A. and Paulusma, D. and van Leeuwen, E.J. (2016) 'Induced disjoint paths in circular-arc graphs in linear time.', Theoretical computer science., 640 . pp. 70-83.
Abstract
The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices (si,ti) contains paths P1,…,Pk such that Pi connects si and ti for i=1,…,k, and Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their ends) for 1≤i<j≤k. We present a linear-time algorithm that solves Induced Disjoint Paths and finds the corresponding paths (if they exist) on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (si,ti) are not necessarily distinct. In both cases, if a representation of the graph is given, then the algorithms run in O(n+k) time.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (374Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1016/j.tcs.2016.06.003 |
| Publisher statement: | © 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | 06 June 2016 |
| Date deposited: | 30 June 2016 |
| Date of first online publication: | 09 June 2016 |
| Date first made open access: | 09 June 2017 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
