The Directed Subgraph Homeomorphism Problem.
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 algorithm is given. Author
- Theoretical Mathematics