Distributed minimum dominating set approximations in restricted families of graphs
type: Item
instance of: scholarly article
title: Distributed minimum dominating set approximations in restricted families of graphs
zbMATH Open document ID: 1271.68070
author: Christoph Lenzen
author: Yvonne Anne Pignolet
author: Roger Wattenhofer
published in: Distributed Computing
publication date: 2013-08-26T00:00:00Z
Mathematics Subject Classification ID: 68M14
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 6201552
zbMATH Keywords: upper bound
zbMATH Keywords: lower bound
zbMATH Keywords: unit disk
zbMATH Keywords: bounded arboricity
zbMATH Keywords: planar
MaRDI profile type: Publication
full work available at URL: s00446-013-0186-z
OpenAlex ID: W2048769918
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Complexity of network synchronization
cites work: Distributed (δ+1)-coloring in linear (in δ) time
cites work: Self-stabilizing systems in spite of distributed control
cites work: Unit disk graphs
cites work: Distributed Almost Exact Approximations for Minor-Closed Families
cites work: Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
cites work: Fast Distributed Approximations in Planar Graphs
cites work: On the Complexity of Distributed Network Decomposition
cites work: Q3577833
cites work: Q4198056
cites work: Approximation algorithms for combinatorial problems
cites work: A fast and simple randomized parallel algorithm for maximal matching
cites work: Probabilistic algorithms for the wake-up problem in single-hop radio networks
cites work: Distributed approximation of capacitated dominating sets
cites work: Local Computation
cites work: Constant-time distributed dominating set approximation
cites work: Leveraging Linial’s Locality Limit
cites work: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Simple heuristics for unit disk graphs
cites work: An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
cites work: Maximal independent sets in radio networks
cites work: A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Q4527015
cites work: A log-star distributed maximal independent set algorithm for growth-bounded graphs
cites work: What Is the Use of Collision Detection (in Wireless Networks)?
cites work: Q4228498
cites work: Über eine Eigenschaft der ebenen Komplexe
cites work: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
DOI: 10.1007/S00446-013-0186-Z
Recommended article: Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
Recommended article: Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
Recommended article: Q4318768
Recommended article: Distributed Dominating Set Approximations beyond Planar Graphs
Recommended article: Distributed approximation of capacitated dominating sets
Recommended article: A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET
Recommended article: Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
Recommended article: Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
Recommended article: Constant-time distributed dominating set approximation
description: scientific article; zbMATH DE number 6201552