Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435178 | Theoretical Computer Science | 2016 | 14 Pages |
Abstract
The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices (si,ti)(si,ti) contains paths P1,…,PkP1,…,Pk such that PiPi connects sisi and titi for i=1,…,ki=1,…,k, and PiPi and PjPj have neither common vertices nor adjacent vertices (except perhaps their ends) for 1≤i
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen,