Minimum Dominating Set Approximation in Graphs of Bounded Arboricity

DOI10.1007/978-3-642-15763-9_48zbMath1290.68130OpenAlexW1523755288MaRDI QIDQ3588326

Roger Wattenhofer, Christoph Lenzen

Publication date: 10 September 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15763-9_48

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (24)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Tight approximation bounds for dominating set on graphs of bounded arboricity ⋮ Distributed algorithms for random graphs ⋮ Geometric dominating-set and set-cover via local-search ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ Greed is good for deterministic scale-free networks ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ A Constructive Arboricity Approximation Scheme ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs ⋮ An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity ⋮ Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity