Symmetry breaking depending on the chromatic number or the neighborhood growth
DOI10.1016/J.TCS.2012.09.004zbMATH Open1416.68140OpenAlexW2023634316MaRDI QIDQ392191FDOQ392191
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
Recommendations
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)
Cites Work
- Trading bit, message, and time complexity of distributed algorithms
- Complexity of network synchronization
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- A new technique for distributed symmetry breaking
- New approximation algorithms for graph coloring
- Simple distributed \(\Delta+1\)-coloring of graphs
- On the complexity of distributed graph coloring
- Fast randomized algorithms for distributed edge coloring (extended abstract)
- New approximation guarantee for chromatic number
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
- Chromatic number, girth and maximal degree
- Fast distributed graph coloring with \(O(\Delta)\) colors
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- Toward more localized local algorithms, removing assumptions concerning global knowledge
- On the complexity of distributed graph coloring with local minimality constraints
- A fast parallel algorithm to color a graph with Δ colors
- Fast Distributed Algorithms for Brooks–Vizing Colorings
- Deterministic distributed vertex coloring in polylogarithmic time
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
Cited In (11)
- A new technique for distributed symmetry breaking
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Lessons from the congested clique applied to MapReduce
- Distributed Symmetry Breaking on Power Graphs via Sparsification
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Distributed Lower Bounds for Ruling Sets
- Distributed reconfiguration of maximal independent sets
- Node and edge averaged complexities of local graph problems
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Distributed Reconfiguration of Maximal Independent Sets
- Improved distributed \(\Delta\)-coloring
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)
