Symmetry breaking depending on the chromatic number or the neighborhood growth

DOI10.1016/j.tcs.2012.09.004zbMath1416.68140OpenAlexW2023634316MaRDI QIDQ392191

Mohammad Hasan, H. S. Yoon

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

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

Related Items (10)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Distributed reconfiguration of maximal independent sets ⋮ Node and edge averaged complexities of local graph problems ⋮ Lessons from the congested clique applied to MapReduce ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Improved distributed \(\Delta\)-coloring ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Distributed Lower Bounds for Ruling Sets

Cites Work

• Unnamed Item
• Chromatic number, girth and maximal degree
• Simple distributed \(\Delta+1\)-coloring of graphs
• New approximation guarantee for chromatic number
• Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Toward more localized local algorithms
• On the complexity of distributed graph coloring with local minimality constraints
• Trading Bit, Message, and Time Complexity of Distributed Algorithms
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Complexity of network synchronization
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm to color a graph with Δ colors
• Locality in Distributed Graph Algorithms
• New approximation algorithms for graph coloring
• Fast Distributed Algorithms for Brooks–Vizing Colorings
• Distributed (δ+1)-coloring in linear (in δ) time
• A new technique for distributed symmetry breaking
• Deterministic distributed vertex coloring in polylogarithmic time
• On the complexity of distributed graph coloring
• Fast randomized algorithms for distributed edge coloring
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

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