๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Load balancing by graph coloring, an algorithm

โœ Scribed by R. Jeurissen; W. Layton

Book ID
103931366
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
560 KB
Volume
27
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 colors so that the largest connected group of same color triangles is as small as possible. We prove that it is always possible to have the largest such group containing at most two triangles and give an O(no. of triangles) algorithm for constructing the coloring.

๐Ÿ“œ SIMILAR VOLUMES

V_THR: An Adaptive Load Balancing Algori
V_THR: An Adaptive Load Balancing Algorithm
โœ Pallab Dasgupta; A.K. Majumder; P. Bhattacharya ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 173 KB

This paper presents a new adaptive algorithm for dynamic load balancing on a shared BUS architecture. We present results obtained from simulation studies and queuing analysis, which reflect the relation between the BUS contention and the efficiency of load balancing. The proposed algorithm uses a sc

An improved diffusion algorithm for dyna
An improved diffusion algorithm for dynamic load balancing
โœ Y.F. Hu; R.J. Blake ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 231 KB

Diusion type algorithms [1,3,11] are some of the most popular algorithms for scheduling in dynamic load balancing. It is known however that this type of algorithm can suer from slow convergence. In this paper the performance of the diusion type algorithms is improved, while retaining the nearest nei

An optimal migration algorithm for dynam
An optimal migration algorithm for dynamic load balancing
โœ HU, Y. F.; BLAKE, R. J.; EMERSON, D. R. ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 207 KB ๐Ÿ‘ 2 views

The problem of redistributing the work load on parallel computers is considered. An optimal redistribution algorithm, which minimises the Euclidean norm of the migrating load, is derived. The relationship between this algorithm and some existing algorithms is discussed and the convergence of the new