Golovach, P.A. and Paulusma, D. and van Leeuwen, E.J. (2014) 'Induced disjoint paths in circular-arc graphs in linear time.', in 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, 25-27 June 2014 ; revised selected papers. Berlin, Heidelberg: Springer, pp. 225-237. Lecture notes in computer science. (8747).
The Induced Disjoint Paths problem is to test whether a graph G 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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (321Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-319-12340-0_19|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-12340-0_19|
|Date accepted:||No date available|
|Date deposited:||17 January 2015|
|Date of first online publication:||2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|