|
|||||
|
|
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 等数据库收录！ | |