Skip to main content

Research Repository

Advanced Search

Induced disjoint paths in circular-arc graphs in linear time

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

Induced disjoint paths in circular-arc graphs in linear time Thumbnail


Authors

P.A. Golovach

E.J. van Leeuwen



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

Files





You might also like



Downloadable Citations