Some simple distributed algorithms for sparse networks

DOI10.1007/PL00008932zbMath1448.68474WikidataQ56269095 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 computing; vertex colouring; maximal matching; edge colouring; maximal independent set; sparse networks

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W15: Distributed algorithms

Related Items

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, Almost global problems in the LOCAL model, Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs, Distributed Graph Algorithms and their Complexity: An Introduction, Distributed deterministic edge coloring using bounded neighborhood independence, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks, Distributed algorithms for random graphs, The coverage-control optimization in sensor network subject to sensing area, Linear-in-\(\varDelta \) lower bounds 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, Best of two local models: centralized local and distributed local algorithms, Almost global problems in the LOCAL model, Distributed backup placement, Linial for lists, Improved deterministic distributed matching via rounding, Improved distributed degree splitting and edge coloring, Combinatorial algorithms for distributed graph coloring, Toward more localized local algorithms: removing assumptions concerning global knowledge, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Optimal distributed covering algorithms

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