On the Complexity of Distributed Network Decomposition

DOI10.1006/jagm.1996.0017zbMath0844.68005OpenAlexW1998643836MaRDI QIDQ4876697

Aravind Srinivasan, Alessandro Panconesi

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

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

Related Items (26)

Distributed independent sets in interval and segment intersection graphs ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Distributed algorithms for random graphs ⋮ Distributed reconfiguration of maximal independent sets ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Computing large independent sets in a single round ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Randomized distributed decision ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ Dynamic networks of finite state machines ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Distributed backup placement ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Distributed coloring algorithms for triangle-free graphs

This page was built for publication: On the Complexity of Distributed Network Decomposition