A new technique for distributed symmetry breaking

DOI10.1145/1835698.1835760zbMath1315.68275OpenAlexW2119761906MaRDI QIDQ5176204

No author found.

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1835698.1835760

zbMATH Keywords

parallel algorithmssymmetry breakingcoloringlocal algorithmsnetwork decomposition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Tight bounds for parallel randomized load balancing ⋮ Can we locally compute sparse connected subgraphs? ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed coloring of hypergraphs ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Randomized distributed decision ⋮ Bounds on contention management algorithms ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Distributed coloring algorithms for triangle-free graphs

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

This page was built for publication: A new technique for distributed symmetry breaking