The subgraph homeomorphism problem

DOI10.1145/800133.804330zbMath1282.68183OpenAlexW1990106480MaRDI QIDQ5402539

Ronald L. Rivest, Andrea S. LaPaugh

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

Related Items (17)

Triples in matroid circuits ⋮ The subgraph homeomorphism problem for small wheels ⋮ The directed subgraph homeomorphism problem ⋮ Shortest edge-disjoint paths in graphs ⋮ The subgraph homeomorphism problem ⋮ All normalized anti-monotonic overlap graph measures are bounded ⋮ Disjoint paths in graphs ⋮ Symmetric space-bounded computation ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Steiner trees, partial 2–trees, and minimum IFI networks ⋮ Detecting cycles through three fixed vertices in a graph ⋮ Methods for proving completeness via logical reductions ⋮ Disjoint paths in graphs. (Reprint) ⋮ Disjoint paths in symmetric digraphs ⋮ A minimization version of a directed subgraph homeomorphism problem ⋮ Connectivity and edge-disjoint spanning trees ⋮ Unnamed Item

This page was built for publication: The subgraph homeomorphism problem