Fast algorithms for \textsc{min independent dominating set}

DOI10.1007/978-3-642-13284-1_20zbMATH Open1284.05270OpenAlexW2569523145MaRDI QIDQ3569130FDOQ3569130

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

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

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)

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)