Very fast parallel algorithms for approximate edge coloring
Date
2001
Authors
Han, Yijie
Liang, Weifa
Shen, Xiaojun
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
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�
Description
Keywords
Keywords: Analysis of algorithms; Edge coloring; Graph algorithms; Parallel algorithms; PRAM
Citation
Collections
Source
Discrete Applied Mathematics
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description