An application of the planar separator theorem to counting problems

DOI10.1016/0020-0190(87)90206-7zbMath0653.68064OpenAlexW1989072522MaRDI QIDQ1108031

S. S. Ravi, Harry B. III Hunt

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90206-7

zbMATH Keywords

dynamic programmingplanar separator theoremmaximum independent-sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items (5)

Graph separators: A parameterized view ⋮ Nonserial dynamic programming formulations of satisfiability ⋮ Theory and application of width bounded geometric separators ⋮ Power indices and easier hard problems ⋮ MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING

Cites Work

• Unnamed Item
• Parallel concepts in graph theory
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Planar Formulae and Their Uses
• On the Problem of Partitioning Planar Graphs
• An introduction to chromatic polynomials

This page was built for publication: An application of the planar separator theorem to counting problems