A note on the complexity of minimum dominating set (Q2458924)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the complexity of minimum dominating set |
scientific article |
Statements
A note on the complexity of minimum dominating set (English)
0 references
5 November 2007
0 references
Minimum dominating set is one of the most basic NP-hard problems in graph theory. The currently fastest algorithm to solve this problem for graphs on \(n\) vertices is the trivial \(\Omega (2^n)\) algorithm which enumerates and checks all subsets of the set of vertices. In this paper a simple algorithm which solves this problem in \(O(1.81^n)\) time is presented.
0 references
dominating set
0 references
set cover
0 references
exact algorithms
0 references
