The subgraph homeomorphism problem

DOI10.1016/0022-0000(80)90057-4MaRDI QIDQ1137871zbMATH OpenOpenAlexWikidataFDO

Authors Andrea S. LaPaugh, Ronald L. Rivest

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

common simple cycleinput graphlinear time algorithmNP-completenessopen problemspattern graphpolynomial timesubgraph homeomorphism problem

Mathematics Subject Classification ID

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

Cites work

• Depth-First Search and Linear Graph Algorithms
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3569814 (Why is no real title available?)
• scientific article; zbMATH DE number 3636069 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3298614 (Why is no real title available?)
• scientific article; zbMATH DE number 3308119 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• scientific article; zbMATH DE number 3405971 (Why is no real title available?)
• Network Flow and Testing Graph Connectivity
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• On the existence of certain disjoint arcs in graphs
• Parallel concepts in graph theory
• The directed subgraph homeomorphism problem
• The subgraph homeomorphism problem

Cited in

(17)

• Structure and recognition of graphs with no 6-wheel subdivision
• An approach to the subgraph homeomorphism problem
• Detecting cycles through three fixed vertices in a graph
• A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs
• Algorithms for topology-free and alignment network queries
• An Improved Algorithm for Finding Cycles Through Elements
• scientific article; zbMATH DE number 7306903 (Why is no real title available?)
• Green's function in partial subdivision networks
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• A Trichotomy for Regular Trail Queries
• Brain chains as topological signatures for Alzheimer's disease
• Parameterized algorithms for list \(K\)-cycle
• Multiflows in symmetric digraphs
• (Almost-)optimal FPT algorithm and kernel for T-cycle on planar graphs
• Finding large cycles in Hamiltonian graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: The subgraph homeomorphism problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1137871)