Some simple distributed algorithms for sparse networks

DOI10.1007/PL00008932zbMath1448.68474DBLPjournals/dc/PanconesiR01OpenAlexW2006040238WikidataQ56269095 ScholiaQ56269095MaRDI QIDQ5138354

Alessandro Panconesi, Romeo Rizzi

Publication date: 3 December 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00008932

zbMATH Keywords

distributed computingvertex colouringmaximal matchingedge colouringmaximal independent setsparse networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (27)

Distributed algorithms for random graphs ⋮ Improved deterministic distributed matching via rounding ⋮ Improved distributed degree splitting and edge coloring ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Component stability in low-space massively parallel computation ⋮ Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ Optimal distributed covering algorithms ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ 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 ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ Almost global problems in the LOCAL model ⋮ Distributed backup placement in networks ⋮ Constant-time local computation algorithms ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Combinatorial algorithms for distributed graph coloring ⋮ A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ The coverage-control optimization in sensor network subject to sensing area ⋮ Almost global problems in the LOCAL model ⋮ Distributed backup placement ⋮ Linial for lists

Cites Work

• Analysis of approximate algorithms for edge-coloring bipartite graphs
• Parallel \((\Delta +1)\)-coloring of constant-degree graphs
• Scheduling parallel I/O operations in multiple bus systems
• A faster distributed algorithm for computing maximal matchings deterministically
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms

This page was built for publication: Some simple distributed algorithms for sparse networks