Fast algorithms for min independent dominating set

DOI10.1016/J.DAM.2012.01.003MaRDI QIDQ1941381zbMATH OpenOpenAlexFDO

Authors Vangelis Th. Paschos, Nicolas Bourgeois, F. Della Croce, Bruno Escoffier

Publication date 12 March 2013

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.01.003

zbMATH Keywords

approximation algorithmsexact algorithmsexponential algorithmsmin independent dominating set

Mathematics Subject Classification ID

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

Recommendations

• Fast algorithms for \textsc{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

(26)

• Time-approximation trade-offs for inapproximable problems
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• The many facets of upper domination
• On the complexity of the smallest grammar problem over fixed alphabets
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• Dominating problems in swapped networks
• \textsc{MAX MIN} vertex cover and the size of Betti tables
• On the complexity landscape of the domination chain
• Upper domination: complexity and approximation
• Completion and decomposition of hypergraphs into dominating sets of graphs
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Fast algorithms for \textsc{min independent dominating set}
• On the max min vertex cover problem
• An Efficient Local Search for the Minimum Independent Dominating Set Problem
• Weighted upper edge cover: complexity and approximability
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• When polynomial approximation meets exact computation
• When polynomial approximation meets exact computation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Faster parameterized algorithms for minor containment
• On the parameterized complexity of cosecure domination
• The size of the Betti table of binomial edge ideals

This page was built for publication: Fast algorithms for min independent dominating set

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