Very fast parallel algorithms for approximate edge coloring

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)227-238
Journal / PublicationDiscrete Applied Mathematics
Volume108
Issue number3
Publication statusPublished - 15 Mar 2001
Externally publishedYes

Abstract

This paper presents very fast parallel algorithms for approximate edge coloring. Let log(1)n=logn,log(k)n=log(log(k-1)n), and log*(n)=min{k|log(k)n<1}. It is shown that a graph with n vertices and m edges can be edge colored with (2⌈log1/4log*(n)⌉) c·(⌈Δ/logc/4log*(n)⌉) 2 colors in O(loglog*(n)) time using O(m+n) processors on the EREW PRAM, where Δ is the maximum vertex degree of the graph and c is an arbitrarily large constant. It is also shown that the graph can be edge colored using at most ⌈4Δ1+4/logloglog*(Δ)log 1/2log*(Δ)⌉ colors in O(logΔloglog*(Δ)/logloglog*(Δ)+loglog*(n)) time using O(m+n) processors on the same model. © 2001 Elsevier Science B.V.

Research Area(s)

  • Analysis of algorithms, Edge coloring, Graph algorithms, Parallel algorithms, PRAM

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Citation Format(s)

Very fast parallel algorithms for approximate edge coloring. / Han, Yijie; Liang, Weifa; Shen, Xiaojun.
In: Discrete Applied Mathematics, Vol. 108, No. 3, 15.03.2001, p. 227-238.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review