Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes

DOI10.1007/11785293_16zbMath1141.68529OpenAlexW1512871835MaRDI QIDQ5757876

Serge Gaspers, Dieter Kratsch, Mathieu Liedloff

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_16

Mathematics Subject Classification ID

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

Related Items

\textsc{MAX MIN} vertex cover and the size of Betti tables ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ An exact algorithm for the minimum dominating clique problem ⋮ On the max min vertex cover problem ⋮ Finding a dominating set on bipartite graphs