The directed subgraph homeomorphism problem
S Fortune, J Hopcroft, J Wyllie - Theoretical Computer Science, 1980 - Elsevier
S Fortune, J Hopcroft, J Wyllie
Theoretical Computer Science, 1980•ElsevierThe set of pattern graphs for which the fixed directed subgraph homeomorphism problem is
NP-complete is characterized. A polynomial time algorithm is given for the remaining cases.
The restricted problem where the input graph is a directed acyclic graph is in polynomial
time for all pattern graphs and an algorithm is given.
NP-complete is characterized. A polynomial time algorithm is given for the remaining cases.
The restricted problem where the input graph is a directed acyclic graph is in polynomial
time for all pattern graphs and an algorithm is given.
Abstract
The set of pattern graphs for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.
Elsevier