Improved distributed degree splitting and edge coloring

DOI10.1007/s00446-018-00346-8zbMath1445.68336arXiv1706.04746OpenAlexW3101102136MaRDI QIDQ2189174

Jukka Suomela, Mohsen Ghaffari, Jara Uitto, Yannic Maus, Fabian Kuhn, Juho Hirvonen

Publication date: 15 June 2020

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

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

zbMATH Keywords

edge coloringdiscrepancydistributed graph algorithmsdegree splitting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Related Items (2)

Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Linial for lists

Cites Work

• Unnamed Item
• Unnamed Item
• An improved parallel algorithm for maximal matching
• ``Integer-making theorems
• A note on the Beck-Fiala theorem
• On the Distributed Complexity of Computing Maximal Matchings
• Efficient parallel algorithms for edge coloring problems
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Degree Splitting, Edge Coloring, and Orientations
• Some simple distributed algorithms for sparse networks
• Deterministic distributed edge-coloring with fewer colors
• What can be computed locally?
• A lower bound for the distributed Lovász local lemma
• An Improvement of the Beck–Fiala Theorem
• Distributed deterministic edge coloring using bounded neighborhood independence

This page was built for publication: Improved distributed degree splitting and edge coloring