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

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