Parallel \((\Delta +1)\)-coloring of constant-degree graphs

DOI10.1016/0020-0190(87)90169-4zbMath0653.68068OpenAlexW2009524061MaRDI QIDQ1108036

Serge A. Plotkin, Andrew V. Goldberg

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90169-4

zbMATH Keywords

graph coloringparallel algorithmscomplexity boundsmaximal independent setEREW PRAM

Mathematics Subject Classification ID

Related Items (7)

Coloring unstructured radio networks ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Some simple distributed algorithms for sparse networks ⋮ Unnamed Item ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Introduction to local certification ⋮ Graph theoretical issues in computer networks

Cites Work

• A Las Vegas RNC algorithm for maximum matching
• Complexity of network synchronization
• A Distributed Algorithm for Minimum-Weight Spanning Trees

This page was built for publication: Parallel \((\Delta +1)\)-coloring of constant-degree graphs