|
|||||
|
|
Coloring planar graphs in parallel |
|
| Authors: | Joan F Boyar Howard J Karloff |
| Abstract: | We present NC algorithms for vertex and edge coloring planar graphs. The vertex coloring algorithm 5 colors any planar graph, and the edge coloring algorithm Δ edge colors planar graphs with Δ ≥ 23 (and Δ + 1 edge colors planar graphs with Δ < 23), where Δ is the maximum degree in the graph. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |