The complexity of counting homeomorphs

DOI10.1016/0304-3975(85)90053-2zbMath0565.68043OpenAlexW2093763335MaRDI QIDQ1058852

Colin J. H. McDiarmid, Graham E. Farr

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90053-2

zbMATH Keywords

pathscircuitsnumber of subgraphsminimal nonplanar subgraphssharp-P-completeness

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• The directed subgraph homeomorphism problem
• The node-deletion problem for hereditary properties is NP-complete
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems

This page was built for publication: The complexity of counting homeomorphs