
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Enhancing PC ClusterBased Parallel BranchandBound Algorithms for the Graph Coloring Problem
Satoshi TAOKA Daisuke TAKAFUJI Toshimasa WATANABE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E91A
No.4
pp.11401149 Publication Date: 2008/04/01 Online ISSN: 17451337
DOI: 10.1093/ietfec/e91a.4.1140 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa) Category: Keyword: parallel branchandbound algorithms, combinatorial optimization problems, MPI, optimum solutions,
Full Text: PDF>>
Summary:
A branchandbound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon nodevariable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sendingnode selection strategy). In this paper, for the graph coloring problem, we propose some sendingnode selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.

