Fast algorithms for min independent dominating set

DOI10.1016/j.dam.2012.01.003zbMath1259.05161OpenAlexW2151423246MaRDI QIDQ1941381

Vangelis Th. Paschos, Nicolas Bourgeois, Frederico 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

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

Related Items (19)

Dominating problems in swapped networks ⋮ Completion and decomposition of hypergraphs into dominating sets of graphs ⋮ \textsc{MAX MIN} vertex cover and the size of Betti tables ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ 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 ⋮ When polynomial approximation meets exact computation ⋮ On the max min vertex cover problem ⋮ When polynomial approximation meets exact computation ⋮ On the Complexity Landscape of the Domination Chain ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Upper Domination: Complexity and Approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ An Efficient Local Search for the Minimum Independent Dominating Set Problem

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