A polynomial-time approximation to a minimum dominating set in a graph

DOI10.1016/J.TCS.2022.07.020MaRDI QIDQ2166772zbMATH OpenOpenAlexWikidataFDO

Authors F. A. Hernández-Mira, Ernesto Parra Inza, Jose M. Sigarreta, Nodari Vakhania

Publication date 25 August 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.04560

zbMATH Keywords

approximation algorithmapproximation ratiodominating setgraphtime complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A greedy approximation for minimum connected dominating sets
• A unified greedy approximation for several dominating set problems
• Minimum connected dominating sets in finite graphs
• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets

Cites work

• k-Degenerate Graphs
• A Greedy Heuristic for the Set-Covering Problem
• A linear algorithm for the domination number of a series-parallel graph
• A linear algorithm for the domination number of a tree
• A measure \& conquer approach for the analysis of exact algorithms
• A note on the k-domination number of a graph
• Algorithms – ESA 2004
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Approximating fault-tolerant domination in general graphs
• Approximation algorithms for connected dominating sets
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation schemes for wireless networks
• Constant-time distributed dominating set approximation
• Dominating sets in social network graphs
• Domination in Geometric Intersection Graphs
• Exact algorithms for dominating set
• Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
• Greedy domination on biclique-free graphs
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 6469213 (Why is no real title available?)
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On the clique-width of some perfect graph classes
• The secure domination problem in cographs
• What cannot be computed locally!

Cited in

(10)

• A note on the complexity of minimum dominating set
• scientific article; zbMATH DE number 3929037 (Why is no real title available?)
• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• scientific article; zbMATH DE number 1445364 (Why is no real title available?)
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
• Exact and heuristic algorithms for the domination problem
• Algorithms for the global domination problem
• Title not available (Why is no real title available?)
• Approximating the minimum independent dominating set in perturbed graphs

This page was built for publication: A polynomial-time approximation to a minimum dominating set in a graph

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