LOAD BALANCING BY GRAPH-COLORING, AN ALGORITHM

Authors
JEURISSEN R LAYTON W
Citation
R. Jeurissen et W. Layton, LOAD BALANCING BY GRAPH-COLORING, AN ALGORITHM, Computers & mathematics with applications, 27(3), 1994, pp. 27-32
Citations number
8
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
27
Issue
3
Year of publication
1994
Pages
27 - 32
Database
ISI
SICI code
0898-1221(1994)27:3<27:LBBGAA>2.0.ZU;2-Q
Abstract
Motivated by an application to load balancing in data-parallel finite element methods, we consider the following coloring question. Color an arbitrary, edge-to-edge triangulation T of a planar domain with two c olors so that the largest connected group of same color triangles is a s small as possible. We prove that it is always possible to have the l argest such group containing at most two triangles and give an O(no. o f triangles) algorithm for constructing the coloring.