Authors: Stevanović, Dragan 
Title: Remarks on dynamic load balancing of integer loads and integral graphs
Journal: Applied Mathematics and Computation
Volume: 226
First page: 38
Last page: 43
Issue Date: 1-Jan-2014
Rank: M21
ISSN: 0096-3003
DOI: 10.1016/j.amc.2013.10.053
Abstract: 
Cvetković et al. (2010) [3] presented an algorithm for dynamic load balancing in discrete load model based on the eigenvectors of the adjacency matrix of the processor network. In case of integral graphs, whose eigenvalues are integers and whose eigenvector basis may be chosen to consist of integers only, this algorithm executes in integer arithmetic, providing an argument for the use of integral graphs as suitable candidates for processor networks. It is observed here that this algorithm, however, is not capable of balancing all integer load distributions. After specifying a necessary and sufficient condition for properly managing all integer load distributions, it becomes apparent that the proposed algorithm does not actually depend on the integrality of eigenvectors, but on employing a set of balancing flows carrying a unit load from a fixed vertex to each of the remaining vertices in the graph. Such sets exist for every connected graph and, thus, yield a simple load balancing algorithm that can be executed in integer arithmetic for every processor network.
Keywords: Dynamic load balancing | Integral graphs | Unit size tokens
Publisher: Elsevier
Project: Graph theory and mathematical programming with applications in chemistry and computer science 
Slovenian Agency for Research, projects P1-0285 and J1-4021

Show full item record

SCOPUSTM   
Citations

1
checked on Dec 3, 2024

Page view(s)

14
checked on Dec 3, 2024

Google ScholarTM

Check

Altmetric

Altmetric


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