An optimal maximal independent set algorithm for bounded-independence graphs
From MaRDI portal
Publication:992507
parallel algorithmdominating setmaximal independent setsymmetry breakingcoloringsensor networkconnected dominating setunit disk graphad hoc networkmaximal matchinglocal algorithmradio networkbounded-independence graphgrowth bounded graph
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15) Distributed systems (68M14)
Recommendations
- scientific article; zbMATH DE number 1003268
- On the maximum independent set problem in graphs of bounded maximum degree
- Algorithms for maximum independent set in convex bipartite graphs
- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
- scientific article; zbMATH DE number 1182770
- scientific article; zbMATH DE number 3881891
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- scientific article; zbMATH DE number 1305487
- The complexity of some problems on maximal independent sets in graphs
- Publication:4892322
Cites work
- 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
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- Coloring unstructured wireless multi-hop networks
- Deterministic coin tossing with applications to optimal parallel list ranking
- Distributed Computing
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Locality in Distributed Graph Algorithms
- On the locality of bounded growth
- Parallel Symmetry-Breaking in Sparse Graphs
- Sorting in linear time?
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- What cannot be computed locally!
Cited in
(31)- Computing maximum independent set on outerstring graphs and their relatives
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- scientific article; zbMATH DE number 5842466 (Why is no real title available?)
- Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
- Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
- A priori optimization for the probabilistic maximum independent set problem
- Distributed independent sets in interval and segment intersection graphs
- Finding a maximal weighted independent set in wireless networks
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Distributed Lower Bounds for Ruling Sets
- Distributed large independent sets in one round on bounded-independence graphs
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- An algorithm for the maximum weight independent set problem on outerstring graphs
- Targeted Branching for the Maximum Independent Set Problem
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Distributed coloring and the local structure of unit-disk graphs
- An exact algorithm for maximum independent set in degree-5 graphs
- Optimal nearest neighbor queries in sensor networks
- Leveraging Linial’s Locality Limit
- Distributed Computing
- Computing large independent sets in a single round
- Maximal independent sets in multichannel radio networks
- An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
- Enabling minimal dominating set in highly dynamic distributed systems
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
This page was built for publication: An optimal maximal independent set algorithm for bounded-independence graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q992507)
