A polynomial-time approximation to a minimum dominating set in a graph
From MaRDI portal
Publication:2166772
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
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
