The subgraph homeomorphism problem

DOI10.1145/800133.804330MaRDI QIDQ5402539zbMATH OpenOpenAlexFDO

Authors Andrea S. LaPaugh, Ronald L. Rivest

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.309.8992

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Paths and cycles (05C38)

Recommendations

• An approach to the subgraph homeomorphism problem
• An exact algorithm for subgraph homeomorphism
• On Exact Complexity of Subgraph Homeomorphism
• scientific article; zbMATH DE number 140477
• O(n2.5) time algorithms for the subgraph homeomorphism problem on trees

Cited in

(28)

• Connectivity and edge-disjoint spanning trees
• The subgraph homeomorphism problem
• Detecting cycles through three fixed vertices in a graph
• Symmetric space-bounded computation
• All normalized anti-monotonic overlap graph measures are bounded
• scientific article; zbMATH DE number 140477 (Why is no real title available?)
• Searching forK_3,3in linear time
• Dichotomies for tree minor containment with structural parameters
• Subgraph homeomorphism via the edge addition planarity algorithm
• The directed subgraph homeomorphism problem
• Disjoint paths in symmetric digraphs
• Triples in matroid circuits
• Disjoint paths in graphs
• Methods for proving completeness via logical reductions
• Revising the Fellows-Kaschube \(K_{3,3}\) search
• An approach to the subgraph homeomorphism problem
• A minimization version of a directed subgraph homeomorphism problem
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• scientific article; zbMATH DE number 682490 (Why is no real title available?)
• The subgraph homeomorphism problem for small wheels
• An exact algorithm for subgraph homeomorphism
• Disjoint paths in graphs. (Reprint)
• On Exact Complexity of Subgraph Homeomorphism
• Shortest edge-disjoint paths in graphs
• Dichotomies for tree minor containment with structural parameters
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• On the subgraph epimorphism problem
• Steiner trees, partial 2–trees, and minimum IFI networks

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 Q5402539)