Xiangdong Yu, Moti Yung
Theoretical Computer Science
We present two algorithms which color edges of every planar graph G with max(Δ(G), 19) colors. Therefore both algorithms produce an optimal coloring if Δ(G) ≥ 19. The first one is a linear-time sequential algorithm. The second one is a parallel EREW PRAM algorithm which runs in O(log2n) time using O(n) processors. Both algorithms are based on reduction techniques analogous to techniques used previously for vertex coloring, and both improve the best known sequential and parallel algorithms. The results are generalized to constant-genus graphs. © 1989.
Xiangdong Yu, Moti Yung
Theoretical Computer Science
Bülent Yener, Yoram Ofek, et al.
IEEE/ACM Transactions on Networking
Marcin Bienkowski, Jarosław Byrka, et al.
Journal of Scheduling
Yehuda Afek, Gad M. Landau, et al.
Information and Computation