The subgraph homeomorphism problem

DOI10.1016/0022-0000(80)90057-4zbMath0429.68060OpenAlexW2045426033WikidataQ56235097 ScholiaQ56235097MaRDI QIDQ1137871

Ronald L. Rivest, Andrea S. LaPaugh

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90057-4

zbMATH Keywords

NP-completenesslinear time algorithmpolynomial timeopen problemssubgraph homeomorphism problempattern graphcommon simple cycleinput graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

An Improved Algorithm for Finding Cycles Through Elements, A Trichotomy for Regular Trail Queries, Parameterized algorithms for list \(K\)-cycle, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs, Detecting cycles through three fixed vertices in a graph, Algorithms for topology-free and alignment network queries, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, Finding large cycles in Hamiltonian graphs, Multiflows in symmetric digraphs, Green's function in partial subdivision networks, Structure and recognition of graphs with no 6-wheel subdivision, Unnamed Item, Unnamed Item, An approach to the subgraph homeomorphism problem

Uses Software

• Algorithm 447

Cites Work

• The directed subgraph homeomorphism problem
• Parallel concepts in graph theory
• On the existence of certain disjoint arcs in graphs
• Network Flow and Testing Graph Connectivity
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The subgraph homeomorphism problem
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item