Distributed minimum dominating set approximations in restricted families of graphs
From MaRDI portal
Publication:360271
DOI10.1007/S00446-013-0186-ZzbMATH Open1271.68070OpenAlexW2048769918MaRDI QIDQ360271FDOQ360271
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
Recommendations
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
- scientific article; zbMATH DE number 708868
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed approximation of capacitated dominating sets
- A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Constant-time distributed dominating set approximation
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Unit disk graphs
- Über eine Eigenschaft der ebenen Komplexe
- Self-stabilizing systems in spite of distributed control
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Complexity of network synchronization
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Maximal independent sets in radio networks
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- A fast and simple randomized parallel algorithm for maximal matching
- Probabilistic algorithms for the wake-up problem in single-hop radio networks
- 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
- Title not available (Why is that?)
- Simple heuristics for unit disk graphs
- On the Complexity of Distributed Network Decomposition
- Distributed (δ+1)-coloring in linear (in δ) time
- Distributed Almost Exact Approximations for Minor-Closed Families
- Constant-time distributed dominating set approximation
- Distributed approximation of capacitated dominating sets
Cited In (25)
- Fast Distributed Approximation for Max-Cut
- Local certification of graphs with bounded genus
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- Compact distributed certification of planar graphs
- Distributed domination on sparse graph classes
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Property testing of planarity in the \textsf{CONGEST} model
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Distributed Dominating Set Approximations beyond Planar Graphs
- A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem
- Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Near-optimal distributed dominating set in bounded arboricity graphs
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- Distributed approximation of capacitated dominating sets
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Local planar domination revisited
- Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Distributed minimum dominating set approximations in restricted families of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q360271)
