A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
From MaRDI portal
Publication:2166266
DOI10.1016/j.dam.2022.06.006zbMath1495.05201arXiv2012.05869OpenAlexW3113350448WikidataQ113877189 ScholiaQ113877189MaRDI QIDQ2166266
A. Karim Abu-Affash, Paz Carmi, Adi Krasin
Publication date: 24 August 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.05869
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm for optimal \(k\)-hop dominating set of a tree
- A linear algorithm for finding a minimum dominating set in a cactus
- Approximation algorithms for combinatorial problems
- A linear algorithm for the domination number of a tree
- Maintenance of a piercing set for intervals with applications
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Fast stabbing of boxes in high dimensions
- Distance domination and distance irredundance in graphs
- Distance domination in graphs with given minimum and maximum degree
- Algorithmic aspects of the \(k\)-domination problem in graphs
- A lower bound for the distance \(k\)-domination number of trees
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- R -Domination in Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Lower Bounds on the Distance Domination Number of a Graph
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- Optimal dynamic program for r-domination problems over tree decompositions
- Approximation and Online Algorithms
