Combinatorial bounds via measure and conquer
Open Access
- 1 November 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 5 (1) , 1-17
Abstract
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O (1.7159 n ). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159 n , thus improving on the trivial O (2 n /√ n ) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O (2.8718 n ) algorithm for the domatic number problem.Keywords
Funding Information
- INTAS (04-77-7173)
- Russian Foundation for Basic Research (08-01-00516)
This publication has 20 references indexed in Scilit:
- Set Partitioning via Inclusion-ExclusionSIAM Journal on Computing, 2009
- Exact Algorithms for Exact Satisfiability and Number of Perfect MatchingsAlgorithmica, 2007
- An improved exact algorithm for the domatic number problemInformation Processing Letters, 2007
- A new algorithm for optimal 2-constraint satisfaction and its implicationsTheoretical Computer Science, 2005
- On the number of maximal bipartite subgraphs of a graphJournal of Graph Theory, 2004
- Small Maximal Independent Sets and Faster Exact Graph ColoringJournal of Graph Algorithms and Applications, 2003
- A deterministic (2−2/(k+1))n algorithm for k-SAT based on local searchTheoretical Computer Science, 2002
- Finding a Maximum Independent SetSIAM Journal on Computing, 1977
- A note on the complexity of the chromatic number problemInformation Processing Letters, 1976
- On cliques in graphsIsrael Journal of Mathematics, 1965