On the Complexity of Distributed Network Decomposition

DOI10.1006/JAGM.1996.0017MaRDI QIDQ4876697zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

network decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

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

Cited in

(34)

• Distributed Strong Diameter Network Decomposition
• Distributed independent sets in interval and segment intersection graphs
• Fast deterministic distributed algorithms for sparse spanners
• Distributed algorithms for random graphs
• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Low-diameter graph decomposition is in NC
• 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 minimum dominating set approximations in restricted families of graphs
• Distributed Lower Bounds for Ruling Sets
• Distributed reconfiguration of maximal independent sets
• scientific article; zbMATH DE number 4001887 (Why is no real title available?)
• Distributed coloring algorithms for triangle-free graphs
• Distributed algorithms for covering, packing and maximum weighted matching
• Computing large independent sets in a single round
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Distributed backup placement
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• 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)