Abstract | ||
---|---|---|
An NC algorithm for the Δ vertex coloring problem is given. The polynomial algorithm implied by Brooks' theorem seems to be highly sequential. To exploit the power of parallel processing we introduce a novel partition of the graph which may find applications elsewhere. |
Year | DOI | Venue |
---|---|---|
1988 | 10.1016/0196-6774(88)90006-5 | Journal of Algorithms |
Keywords | Field | DocType |
fast parallel algorithm,parallel algorithm | Graph theory,Discrete mathematics,Edge coloring,Combinatorics,Vertex (geometry),Claw-free graph,Parallel algorithm,Vertex (graph theory),Cubic graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
9 | 1 | 0196-6774 |
Citations | PageRank | References |
5 | 1.05 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mauricio Karchmer | 1 | 571 | 54.29 |
Joseph Naor | 2 | 8 | 3.53 |