Near-optimal, distributed edge colouring via the nibble method

DOI10.1016/S0304-3975(98)00022-XzbMath0913.68146OpenAlexW2052354487MaRDI QIDQ1274333

David A. Grable, Alessandro Panconesi, Devdatt P. Dubhashi

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00022-x

zbMATH Keywords

randomized algorithmsdistributed algorithmsedge colouringlarge deviation inequalities

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

(Probabilistic) recurrence relations revisited ⋮ Probabilistic recurrence relations revisited ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Number of 1-factorizations of regular high-degree graphs ⋮ Towards the linear arboricity conjecture ⋮ Constructing processes with prescribed mixing coefficients ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Randomized Δ-edge colouring via exchanges of complex colours

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the chromatic index for hypergraphs
• On a packing and covering problem
• Asymptotically good coverings
• Near perfect coverings in graphs and hypergraphs
• Upper bounds for static resource allocation in a distributed system
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• Scheduling parallel I/O operations in multiple bus systems
• Nearly perfect matchings in regular simple hypergraphs
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Efficient parallel algorithms for edge coloring problems
• The NP-Completeness of Edge-Coloring
• Simulating (log ^c n )-wise independence in NC
• A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
• NP completeness of finding the chromatic index of regular graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• (Probabilistic) recurrence relations revisited