Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs |
| |
Authors: | He Xin |
| |
Affiliation: | 1.Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA ; |
| |
Abstract: | We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n 3/2) sequential time, orO(log4 n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3 n) time withO(n) processors on a PRAM. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|