On the Complexity of Distributed Network Decomposition
From MaRDI portal
Publication:4876697
DOI10.1006/JAGM.1996.0017zbMATH Open0844.68005OpenAlexW1998643836MaRDI QIDQ4876697FDOQ4876697
Authors: Alessandro Panconesi, Aravind Srinivasan 
Publication date: 6 May 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6128
Recommendations
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
- Distributed Strong Diameter Network Decomposition
- Fast distributed network decompositions and covers
Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)
Cited In (34)
- Distributed Strong Diameter Network Decomposition
- Distributed independent sets in interval and segment intersection graphs
- Fast deterministic distributed algorithms for sparse spanners
- Title not available (Why is that?)
- Distributed algorithms for random graphs
- SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
- DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
- Low-diameter graph decomposition is in NC
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Distributed coloring in sparse graphs with fewer colors
- Some LCP decompositions of multistage interconnection networks
- Fast network decomposition
- Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
- Distributed computing with advice: information sensitivity of graph coloring
- Local Maps: New Insights into Mobile Agent Algorithms
- On the complexity of distributed graph coloring with local minimality constraints
- Distributed graph algorithms and their complexity: an introduction
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Distributed Lower Bounds for Ruling Sets
- Distributed minimum dominating set approximations in restricted families of graphs
- Distributed reconfiguration of maximal independent sets
- Title not available (Why is that?)
- Distributed coloring algorithms for triangle-free graphs
- Computing large independent sets in a single round
- Distributed algorithms for covering, packing and maximum weighted matching
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Distributed backup placement
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Distributed Reconfiguration of Maximal Independent Sets
This page was built for publication: On the Complexity of Distributed Network Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4876697)
