Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333168 | Journal of Discrete Algorithms | 2009 | 5 Pages |
Abstract
We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2nâpnO(1) or in time 3nâpnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andrzej Lingas, Martin Wahlen,