Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number

DOI10.1007/978-3-642-13073-1_8zbMath1284.05318OpenAlexW1763976135MaRDI QIDQ3562993

Johan M. M. van Rooij

Publication date: 28 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13073-1_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Bipartition polynomials, the Ising model, and domination in graphs

This page was built for publication: Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number