A log-star distributed maximal independent set algorithm for growth-bounded graphs
\textsc{Connected Dominating Sets}\textsc{Maximal Independent Set}ad hoc networkscoloringdominating setsgrowth bounded graphslocal algorithmsparallel algorithmsradio networkssensor networkssymmetry breakingunit disk graphs
Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Distributed Computing
- An Improved Distributed Algorithm for Maximal Independent Set
- An optimal maximal independent set algorithm for bounded-independence graphs
- A new distributed approximation algorithm for the maximum weight independent set problem
- A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
- Improved distributed approximations for maximum independent set
- Distributed approximation of maximum independent set and maximum matching
- A distributed algorithm for k-dominating sets
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Distributed backup placement
- Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Coloring unstructured radio networks
- Can we locally compute sparse connected subgraphs?
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- On the computation of fixed points in Boolean networks
- Distributed strong diameter network decomposition
- Simple distributed spanners in dense congest networks
- Topology control and routing in ad hoc networks
- Nearly optimal local broadcasting in the SINR model with feedback
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Leveraging Linial’s Locality Limit
- Distributed minimum dominating set approximations in restricted families of graphs
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Distributed approximation of cellular coverage
- Shifting strategy for geometric graphs without geometry
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
- On the locality of bounded growth
- \textsc{Maximal Independent Sets} in radio networks
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Distributed Computing
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Distributed distance-r covering problems on sparse high-girth graphs
- Distributed deterministic edge coloring using bounded neighborhood independence
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Distributed approximation of capacitated dominating sets
- Distributed MIS in O( n) awake complexity
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
This page was built for publication: A log-star distributed maximal independent set algorithm for growth-bounded graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934330)
