Very fast parallel algorithms for approximate edge coloring

DOI10.1016/S0166-218X(99)00190-0zbMath0967.68120OpenAlexW2035522910WikidataQ127724271 ScholiaQ127724271MaRDI QIDQ5929308

Weifa Liang, Yijie Han, Xiao-Jun Shen

Publication date: 3 September 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00190-0

zbMATH Keywords

edge coloringfast parallel algorithms

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• A constructive proof of Vizing's theorem
• The probabilistic method yields deterministic parallel algorithms
• Parallel algorithms for the edge-coloring and edge-coloring update problems
• Efficient parallel algorithms for edge coloring problems
• The NP-Completeness of Edge-Coloring
• Simulating (log ^c n )-wise independence in NC

This page was built for publication: Very fast parallel algorithms for approximate edge coloring