Skip navigation
Skip navigation

Very fast parallel algorithms for approximate edge coloring

Han, Yijie; Liang, Weifa; Shen, Xiaojun

Description

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�

dc.contributor.authorHan, Yijie
dc.contributor.authorLiang, Weifa
dc.contributor.authorShen, Xiaojun
dc.date.accessioned2015-12-13T22:17:07Z
dc.identifier.issn0166-218X
dc.identifier.urihttp://hdl.handle.net/1885/70997
dc.description.abstractThis 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�
dc.publisherElsevier
dc.sourceDiscrete Applied Mathematics
dc.subjectKeywords: Analysis of algorithms; Edge coloring; Graph algorithms; Parallel algorithms; PRAM
dc.titleVery fast parallel algorithms for approximate edge coloring
dc.typeJournal article
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.citationvolume108
dc.date.issued2001
local.identifier.absfor080110 - Simulation and Modelling
local.identifier.ariespublicationMigratedxPub2507
local.type.statusPublished Version
local.contributor.affiliationHan, Yijie, Electronic Data Systems, Inc.
local.contributor.affiliationLiang, Weifa, College of Engineering and Computer Science, ANU
local.contributor.affiliationShen, Xiaojun, University of Missouri
local.description.embargo2037-12-31
local.bibliographicCitation.startpage227
local.bibliographicCitation.lastpage238
local.identifier.doi10.1016/S0166-218X(99)00190-0
dc.date.updated2015-12-11T07:31:06Z
local.identifier.scopusID2-s2.0-0345817193
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Han_Very_fast_parallel_algorithms_2001.pdf109.97 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator