An efficient algorithm for edge coloring planar graphs with Δ colors

Xin He

doi:10.1016/0304-3975(90)90079-W

An efficient algorithm for edge coloring planar graphs with Δ colors

Xin He

Department of Computer Science and Engineering

University at Buffalo

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

2 Scopus citations

Abstract

We present an efficient algorithm for edge coloring a planar graphG. Let n be the number of vertices and Δ be the maximum degree of G. If Δ ≥33, our algorithm constructs an edge coloring of G using Δ colors. The parallel implementation of the algorithm takes O(log²n) time with O(n) processors. The sequential implementation takes O(n) time.

Original language	English
Pages (from-to)	299-312
Number of pages	14
Journal	Theoretical Computer Science
Volume	74
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(90)90079-W
State	Published - Aug 28 1990

Access to Document

10.1016/0304-3975(90)90079-W

Cite this

@article{cd69713f84804a8ea48d32acc642f55e,

title = "An efficient algorithm for edge coloring planar graphs with Δ colors",

abstract = "We present an efficient algorithm for edge coloring a planar graphG. Let n be the number of vertices and Δ be the maximum degree of G. If Δ ≥33, our algorithm constructs an edge coloring of G using Δ colors. The parallel implementation of the algorithm takes O(log2n) time with O(n) processors. The sequential implementation takes O(n) time.",

author = "Xin He",

year = "1990",

month = aug,

day = "28",

doi = "10.1016/0304-3975(90)90079-W",

language = "English",

volume = "74",

pages = "299--312",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - An efficient algorithm for edge coloring planar graphs with Δ colors

AU - He, Xin

PY - 1990/8/28

Y1 - 1990/8/28

N2 - We present an efficient algorithm for edge coloring a planar graphG. Let n be the number of vertices and Δ be the maximum degree of G. If Δ ≥33, our algorithm constructs an edge coloring of G using Δ colors. The parallel implementation of the algorithm takes O(log2n) time with O(n) processors. The sequential implementation takes O(n) time.

AB - We present an efficient algorithm for edge coloring a planar graphG. Let n be the number of vertices and Δ be the maximum degree of G. If Δ ≥33, our algorithm constructs an edge coloring of G using Δ colors. The parallel implementation of the algorithm takes O(log2n) time with O(n) processors. The sequential implementation takes O(n) time.

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

U2 - 10.1016/0304-3975(90)90079-W

DO - 10.1016/0304-3975(90)90079-W

M3 - Article

SN - 0304-3975

VL - 74

SP - 299

EP - 312

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

An efficient algorithm for edge coloring planar graphs with Δ colors

Abstract

Access to Document

Other files and links

Fingerprint

Cite this