Induced disjoint paths in circular-arc graphs in linear time

Golovach, P.A.; Paulusma, D.; van Leeuwen, E.J.

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

Citation

Golovach, P., Paulusma, D., & van Leeuwen, E. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science, 640, 70-83. https://doi.org/10.1016/j.tcs.2016.06.003

• Journal Article Type: Article
• Acceptance Date: Jun 6, 2016
• Online Publication Date: Jun 9, 2016
• Publication Date: Aug 9, 2016
• Deposit Date: Jun 29, 2016
• Publicly Available Date: Jun 9, 2017
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 640
• Pages: 70-83
• DOI: https://doi.org/10.1016/j.tcs.2016.06.003
• Public URL: https://durham-repository.worktribe.com/output/1401501