An optimal maximal independent set algorithm for bounded-independence graphs
DOI10.1007/S00446-010-0097-1zbMATH Open1231.68092OpenAlexW1980501142MaRDI QIDQ992507FDOQ992507
Authors: J. Martínez 
Publication date: 9 September 2010
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/157549
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
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)
Cites Work
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- What cannot be computed locally!
- Distributed Computing
- A fast and simple randomized parallel algorithm for maximal matching
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Sorting in linear time?
- On the locality of bounded growth
- Parallel Symmetry-Breaking in Sparse Graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Distributed agreement in tile self-assembly
- Coloring unstructured wireless multi-hop networks
- Deterministic coin tossing with applications to optimal parallel list ranking
- A weakly robust PTAS for minimum clique partition in unit disk graphs
Cited In (31)
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Maximal independent sets in multichannel radio networks
- An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
- Distributed independent sets in interval and segment intersection graphs
- Optimal nearest neighbor queries in sensor networks
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Dynamic networks of finite state machines
- Finding a maximal weighted independent set in wireless networks
- Distributed large independent sets in one round on bounded-independence graphs
- Enabling minimal dominating set in highly dynamic distributed systems
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Distributed coloring and the local structure of unit-disk graphs
- A priori optimization for the probabilistic maximum independent set problem
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- Leveraging Linial’s Locality Limit
- Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
- An exact algorithm for maximum independent set in degree-5 graphs
- Distributed Computing
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Targeted Branching for the Maximum Independent Set Problem
- Title not available (Why is that?)
- Distributed Lower Bounds for Ruling Sets
- Computing large independent sets in a single round
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
- An algorithm for the maximum weight independent set problem on outerstring graphs
- Advice complexity of maximum independent set in sparse and bipartite graphs
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- Computing maximum independent set on outerstring graphs and their relatives
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)
