Distributed minimum dominating set approximations in restricted families of graphs
From MaRDI portal
Publication:360271
DOI10.1007/s00446-013-0186-zzbMath1271.68070OpenAlexW2048769918MaRDI QIDQ360271
Christoph Lenzen, Yvonne Anne Pignolet, Roger Wattenhofer
Publication date: 26 August 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-013-0186-z
Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)
Related Items
Fast Distributed Approximation for Max-Cut ⋮ Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Compact distributed certification of planar graphs ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs ⋮ Local planar domination revisited ⋮ Local certification of graphs with bounded genus ⋮ Constant round distributed domination on graph classes with bounded expansion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed approximation of capacitated dominating sets
- A fast and simple randomized parallel algorithm for maximal matching
- Unit disk graphs
- Approximation algorithms for combinatorial problems
- Probabilistic algorithms for the wake-up problem in single-hop radio networks
- Über eine Eigenschaft der ebenen Komplexe
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Local Computation
- An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- What Is the Use of Collision Detection (in Wireless Networks)?
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Complexity of network synchronization
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Locality in Distributed Graph Algorithms
- Self-stabilizing systems in spite of distributed control
- Distributed Computing: A Locality-Sensitive Approach
- Simple heuristics for unit disk graphs
- On the Complexity of Distributed Network Decomposition
- Distributed (δ+1)-coloring in linear (in δ) time
- Maximal independent sets in radio networks
- Distributed Almost Exact Approximations for Minor-Closed Families
- Constant-time distributed dominating set approximation
This page was built for publication: Distributed minimum dominating set approximations in restricted families of graphs
