Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

Xin He

doi:10.1007/BF01840403

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

Xin He

Department of Computer Science and Engineering

University at Buffalo

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takes O(n^3/2) sequential time, or O(log⁴ n) parallel time with O(n³) processors. The sequential implementation of our algorithm takes O(n log n) time. The parallel implementation of our algorithm takes O(log³ n) time with O(n) processors on a PRAM.

Original language	English
Pages (from-to)	545-559
Number of pages	15
Journal	Algorithmica
Volume	5
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01840403
State	Published - Jun 1990

Keywords

4-Coloring algorithm
Perfect graphs
Planar graphs

Access to Document

10.1007/BF01840403

Cite this

@article{3d35f462417846e698d75248a76d0b6b,

title = "Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs",

abstract = "We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takes O(n 3/2) sequential time, or O(log4 n) parallel time with O(n3) processors. The sequential implementation of our algorithm takes O(n log n) time. The parallel implementation of our algorithm takes O(log3 n) time with O(n) processors on a PRAM.",

keywords = "4-Coloring algorithm, Perfect graphs, Planar graphs",

author = "Xin He",

year = "1990",

month = jun,

doi = "10.1007/BF01840403",

language = "English",

volume = "5",

pages = "545--559",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

AU - He, Xin

PY - 1990/6

Y1 - 1990/6

N2 - We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takes O(n 3/2) sequential time, or O(log4 n) parallel time with O(n3) processors. The sequential implementation of our algorithm takes O(n log n) time. The parallel implementation of our algorithm takes O(log3 n) time with O(n) processors on a PRAM.

AB - We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takes O(n 3/2) sequential time, or O(log4 n) parallel time with O(n3) processors. The sequential implementation of our algorithm takes O(n log n) time. The parallel implementation of our algorithm takes O(log3 n) time with O(n) processors on a PRAM.

KW - 4-Coloring algorithm

KW - Perfect graphs

KW - Planar graphs

UR - https://www.scopus.com/pages/publications/52449144999

U2 - 10.1007/BF01840403

DO - 10.1007/BF01840403

M3 - Article

SN - 0178-4617

VL - 5

SP - 545

EP - 559

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this