Efficient parallel algorithms for edge coloring problems

DOI10.1016/0196-6774(87)90026-5zbMath0642.68125OpenAlexW2152453230WikidataQ56390675 ScholiaQ56390675MaRDI QIDQ3783599

David B. Shmoys, Howard J. Karloff

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90026-5

zbMATH Keywords

edge coloringparallel algorithmsNC algorithms

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)

Related Items (13)

The probabilistic method yields deterministic parallel algorithms ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ An NC algorithm for Brooks' theorem ⋮ Improved distributed degree splitting and edge coloring ⋮ Edge coloring graphs with large minimum degree ⋮ Near-optimal distributed edge coloring ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors ⋮ Very fast parallel algorithms for approximate edge coloring ⋮ Generalized edge-colorings of weighted graphs ⋮ Efficient algorithms for path partitions ⋮ Near-optimal, distributed edge colouring via the nibble method

This page was built for publication: Efficient parallel algorithms for edge coloring problems