On the complexity of distributed graph coloring with local minimality constraints
From MaRDI portal
Publication:3057099
DOI10.1002/net.20293zbMath1207.05053OpenAlexW4229960859WikidataQ62048702 ScholiaQ62048702MaRDI QIDQ3057099
Alfredo Navarra, Ralf Klasing, Łukasz Kuszner, Cyril Gavoille, Adrian Kosowski
Publication date: 24 November 2010
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00200127v2/file/RR-6399.pdf
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)
Related Items (6)
Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Linial for lists
Cites Work
- Algorithms for some graph problems on a distributed computational model
- Legal coloring of graphs
- Welsh-Powell opposition graphs
- The train marshalling problem
- Simple distributed \(\Delta+1\)-coloring of graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
- Graph Theory and Probability
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Almost all k-colorable graphs are easy to color
- Locality in Distributed Graph Algorithms
- Fast Distributed Algorithms for Brooks–Vizing Colorings
- On the Complexity of Distributed Network Decomposition
- On the complexity of distributed graph coloring
This page was built for publication: On the complexity of distributed graph coloring with local minimality constraints
