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.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (374Kb)
|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
|Look up in GoogleScholar|