Distributed minimum dominating set approximations in restricted families of graphs
From MaRDI portal
(Redirected from Publication:360271)
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
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256762 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for maximal matching
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Approximation algorithms for combinatorial problems
- Complexity of network synchronization
- Constant-time distributed dominating set approximation
- Distributed Almost Exact Approximations for Minor-Closed Families
- Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
- Distributed Computing: A Locality-Sensitive Approach
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
- Distributed approximation of capacitated dominating sets
- Fast Distributed Approximations in Planar Graphs
- Graph theory
- Leveraging Linial’s Locality Limit
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Local computation: lower and upper bounds
- Locality in Distributed Graph Algorithms
- Minimum dominating set approximation in graphs of bounded arboricity
- On the Complexity of Distributed Network Decomposition
- Probabilistic algorithms for the wake-up problem in single-hop radio networks
- Self-stabilizing systems in spite of distributed control
- Simple heuristics for unit disk graphs
- Unit disk graphs
- What is the use of collision detection (in wireless networks)?
- \textsc{Maximal Independent Sets} in radio networks
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(26)- Local planar domination revisited
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- Near-optimal distributed dominating set in bounded arboricity graphs
- Constant round distributed domination on graph classes with bounded expansion
- Compact distributed certification of planar graphs
- Distributed approximation of capacitated dominating sets
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem
- 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
- 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
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Minimum dominating set approximation in graphs of bounded arboricity
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Local certification of graphs with bounded genus
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free 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
- Fast Distributed Approximation for Max-Cut
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)
