A branch-and-reduce algorithm for finding a minimum independent dominating set

MaRDI QIDQ5403013zbMATH OpenFDO

Authors Serge Gaspers, Mathieu Liedloff

Publication date 25 March 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1744/0.html

zbMATH Keywords

exponential time algorithmsminimum independent dominating setminimum maximal independent set

Mathematics Subject Classification ID

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

Recommendations

• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Fast algorithms for min independent dominating set
• Fast algorithms for \textsc{min independent dominating set}
• Independent dominating set problem revisited

Cited in

(17)

• On independent sets and bicliques in graphs
• An Efficient Local Search for the Minimum Independent Dominating Set Problem
• Algorithms to determine an independent dominating set of \(\mathrm{ESC}(n,k)\)
• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
• Two algorithms for determining a minimum independent dominating set
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Parameterized and exact algorithms for class domination coloring
• Parameterized and exact algorithms for class domination coloring
• A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks
• Independent dominating set problem revisited
• Iterative construction of the minimum independent dominating sets in hypercube graphs
• Targeted Branching for the Maximum Independent Set Problem
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic
• Fast algorithms for min independent dominating set
• Fast algorithms for \textsc{min independent dominating set}
• Inclusion/exclusion meets measure and conquer

This page was built for publication: A branch-and-reduce algorithm for finding a minimum independent dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5403013)