ausblenden:
Schlagwörter:
Computer Science, Data Structures and Algorithms, cs.DS
Zusammenfassung:
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.
