Approximating Fault-Tolerant Domination in General Graphs

DOI10.1137/1.9781611973037.4zbMath1430.68200OpenAlexW2245780573MaRDI QIDQ5194735

Klaus-Tycho Foerster

Publication date: 17 September 2019

Published in: 2013 Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973037.4

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (8)

Approximating \(k\)-connected \(m\)-dominating sets ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Fault-tolerant total domination via submodular function approximation ⋮ Domination and convexity problems in the target set selection model ⋮ Approximating k-Connected m-Dominating Sets ⋮ Bounds on the 2-domination number ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems

This page was built for publication: Approximating Fault-Tolerant Domination in General Graphs