Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Paper

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

MPS-Authors

/persons/resource/persons98374

van Leeuwen, Erik Jan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

arXiv:1403.0789.pdf
(Preprint), 211KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2014). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. Retrieved from http://arxiv.org/abs/1403.0789.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4060-9

Abstract

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.