A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
From MaRDI portal
Publication:5401393
DOI10.1145/1281100.1281111zbMath1283.68398OpenAlexW2052811387MaRDI QIDQ5401393
Publication date: 13 March 2014
Published in: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/70625
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)
Related Items (21)
A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Impact of locality on location aware unit disk graphs ⋮ Distributed approximation of capacitated dominating sets ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Distributed strong diameter network decomposition ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs ⋮ Leveraging Linial’s Locality Limit ⋮ Improved distributed \(\Delta\)-coloring ⋮ Independent sets in graphs ⋮ A distributed O(1)-approximation algorithm for the uniform facility location problem ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Distributed backup placement ⋮ Distributed Lower Bounds for Ruling Sets ⋮ PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
This page was built for publication: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
