Very fast parallel algorithms for approximate edge coloring
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 227-238 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 108 |
Issue number | 3 |
Publication status | Published - 15 Mar 2001 |
Externally published | Yes |
Link(s)
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.
In: Discrete Applied Mathematics, Vol. 108, No. 3, 15.03.2001, p. 227-238.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review