| No | 172962 |
|---|---|
| 標題（和） | グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能強化 |
| 標題（英） | Enhancing Performance of PC Cluster-based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem |
| 研究会名（和） | 回路とシステム, 信号処理, 通信方式 |
| 研究会名（英） | Circuits and Systems, Signal Processing, Communication Systems |
| 開催年月日 | 2006-03-06 |
| 終了年月日 | 2006-03-07 |
| 会議種別コード | 5 |
| 共催団体名（和） | |
| 資料番号 | CAS2005-121, SIP2005-167, CS2005-114 |
| 抄録（和） | 分枝限定解法は様々な組合わせ最適化問題を解くための最も一般的な解法で\r\nあるが，問題サイズの増加にともない計算時間が指数関数的に増加する．\r\nそのため，計算時間短縮を意図した並列化が考えられる．分枝限定解法においては，分枝の早\r\nい段階においてより最適解に近い暫定解が得られれば，枝刈りが早く起こる可能性\r\nが高くなり計算回数を減らすこと，すなわち，解法の高速化につながる．また，効率的な並列化の\r\nためには各計算機にかかる負荷を均等にすると同時に，通信時間の増加を抑\r\nえる必要もある．本研究では，グラフ彩色問題に対するPCクラスタ上の並列分\r\n枝限定解法に注目し、その性能強化を目指した改良を組み込み，その効果を計算機実験により評価する． |
| 抄録（英） | A branch-and-bound algorithm (BB for short) is the most general technique\r\nto deal with various combinatorial optimization problems. Even if it is\r\nused, computation time is likely to increase exponentially. So we\r\nconsider its parallelization to reduce it. \r\nWe can expect that obtaining a better incumbent \r\nmakes bounding operations appear at early stages\r\nof computation, possibly resulting in short computation time.\r\nIn case of a parallel BB, it is also necessary to balance\r\neach processor load and to prevent increase in communication time．\r\nIn this paper, we focus on a parallel BB for the graph coloring problem,\r\npropose some improvements for it,\r\nand experimentally\r\nevaluate how our modification affect computation time of a parallel BB\r\non a PC cluster network. |
| 収録資料名（和） | 電子情報通信学会技術研究報告 |
| 収録資料の巻号 | Vol.105, No.634,636,638 |
| ページ開始 | 19 |
| ページ終了 | 24 |
| キーワード（和） | グラフ彩色問題,並列分枝限定解法,組合わせ最適化問題,MPI |
| キーワード（英） | Graph coloring problem,Parallel branch-and-bound algorithms,Combinatorial optimization problems,MPI |
| 本文の言語 | ENG |
| 著者（和） | 野村健太郎 |
| 著者（ヨミ） | ノムラ ケンタロウ |
| 著者（英） | Kentaro Nomura |
| 所属機関（和） | 広島大学大学院 |
| 所属機関（英） | Graduate School of Engineering, Hiroshima University |
| 著者（和） | 田岡智志 |
| 著者（ヨミ） | タオカ サトシ |
| 著者（英） | Satoshi Taoka |
| 所属機関（和） | 広島大学大学院 |
| 所属機関（英） | Graduate School of Engineering, Hiroshima University |
| 著者（和） | 渡邉敏正 |
| 著者（ヨミ） | ワタナベ トシマサ |
| 著者（英） | Toshimasa Watanabe |
| 所属機関（和） | 広島大学大学院 |
| 所属機関（英） | Graduate School of Engineering, Hiroshima University |