Distributed deterministic edge coloring using bounded neighborhood independence

DOI10.1007/s00446-012-0167-7zbMath1284.68443arXiv1010.2454OpenAlexW2016190491MaRDI QIDQ5920296

Michael Elkin, Leonid Barenboim

Publication date: 28 March 2014

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.2454

zbMATH Keywords

line-graphsdefective-coloringlegal-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Distributed algorithms for random graphs ⋮ Simple Distributed Spanners in Dense Congest Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling parallel I/O operations in multiple bus systems
• Near-optimal, distributed edge colouring via the nibble method
• Low diameter graph decompositions
• Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Locality in Distributed Graph Algorithms
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Nearly optimal distributed edge coloring in O(log log n) rounds
• Some simple distributed algorithms for sparse networks
• Distributed (δ+1)-coloring in linear (in δ) time
• A new technique for distributed symmetry breaking
• Deterministic distributed vertex coloring in polylogarithmic time
• On the locality of bounded growth
• Locality based graph coloring
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

This page was built for publication: Distributed deterministic edge coloring using bounded neighborhood independence