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

DOI10.1016/j.tcs.2022.07.020OpenAlexW3204841430WikidataQ114129071 ScholiaQ114129071MaRDI QIDQ2166772

Nodari Vakhania, Ernesto Parra Inza, José María Sigarreta-Almira, F. A. Hernández-Mira

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

graphapproximation algorithmdominating settime complexityapproximation ratio

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• A note on the k-domination number of a graph
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Dominating sets in social network graphs
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• A linear algorithm for the domination number of a tree
• Approximation algorithms for connected dominating sets
• The secure domination problem in cographs
• Greedy domination on biclique-free graphs
• A linear algorithm for the domination number of a series-parallel graph
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• A measure & conquer approach for the analysis of exact algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• A Greedy Heuristic for the Set-Covering Problem
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Approximation schemes for wireless networks
• Approximating Fault-Tolerant Domination in General Graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Domination in Geometric Intersection Graphs
• Algorithms – ESA 2004
• What cannot be computed locally!
• k-Degenerate Graphs
• Constant-time distributed dominating set approximation

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