The Directed Subgraph Homeomorphism Problem.

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 algorithm is given. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1978
Accession Number
ADA058452

Entities

People

  • James Wyllie
  • John Hopcroft
  • Steven Fortune

Organizations

  • Department of Computer Science, Cornell University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Commodities
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Guarantees
  • Mathematics
  • Polynomials
  • Sequences
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.