Fast algorithms for \textsc{min independent dominating set}

DOI10.1007/978-3-642-13284-1_20MaRDI QIDQ3569130zbMATH OpenOpenAlexFDO

Authors Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Publication date 17 June 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13284-1_20

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Fast algorithms for min independent dominating set
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• On approximating the minimum independent dominating set

Cited in

(9)

• An Efficient Local Search for the Minimum Independent Dominating Set Problem
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Upper domination: complexity and approximation
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• The many facets of upper domination
• Fast algorithms for min independent dominating set
• Inclusion/exclusion meets measure and conquer

This page was built for publication: Fast algorithms for \textsc{min independent dominating set}

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