Symmetry breaking depending on the chromatic number or the neighborhood growth

DOI10.1016/J.TCS.2012.09.004MaRDI QIDQ392191zbMATHOpenAlexFDO

Authors Johannes Schneider, Michael Elkin, Roger Wattenhofer

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.09.004

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Recommendations

• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• The locality of distributed symmetry breaking
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Neighborhood graphs and distributed Δ+1-coloring
• A new technique for distributed symmetry breaking

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm to color a graph with Δ colors
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• A new technique for distributed symmetry breaking
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Chromatic number, girth and maximal degree
• Complexity of network synchronization
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
• Fast Distributed Algorithms for Brooks–Vizing Colorings
• Fast distributed graph coloring with \(O(\Delta)\) colors
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• Locality in Distributed Graph Algorithms
• New approximation algorithms for graph coloring
• New approximation guarantee for chromatic number
• On the complexity of distributed graph coloring
• On the complexity of distributed graph coloring with local minimality constraints
• Simple distributed \(\Delta+1\)-coloring of graphs
• Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Trading bit, message, and time complexity of distributed algorithms

Cited in

(11)

• Distributed reconfiguration of maximal independent sets
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Distributed Lower Bounds for Ruling Sets
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Distributed Reconfiguration of Maximal Independent Sets
• Improved distributed \(\Delta\)-coloring
• Lessons from the congested clique applied to MapReduce
• A new technique for distributed symmetry breaking
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Node and edge averaged complexities of local graph problems
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees

This page was built for publication: Symmetry breaking depending on the chromatic number or the neighborhood growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392191)