A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
From MaRDI portal
Publication:3522944
DOI10.1007/11917496_8zbMath1167.05331arXiv1009.1381OpenAlexW1581812120MaRDI QIDQ3522944
Mathieu Liedloff, Serge Gaspers
Publication date: 4 September 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.1381
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On Independent Sets and Bicliques in Graphs ⋮ \textsc{MAX MIN} vertex cover and the size of Betti tables ⋮ Iterative construction of the minimum independent dominating sets in hypercube graphs ⋮ Exact algorithms for dominating set ⋮ An exact algorithm for the minimum dominating clique problem ⋮ On the max min vertex cover problem ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
