Tabu Searchのグラフ分割問題への適用と実験的解析

DOI Web Site Web Site 被引用文献10件

書誌事項

タイトル別名
  • An Application of Tabu Search to the Graph Partitioning Problem and its Experimental Analysis
  • Tabu Search ノ グラフ ブンカツ モンダイ エ ノ テキヨウ ト

この論文をさがす

抄録

In this paper, we report on an application of tabu search to the graph partitioning problem which has applications on circuit board wiring and program segmentation. We discuss how to adapt tabu search to the graph partitioning problem and compare the performance with simulated annealing, another variant of local search incorporating randomized technique. Numerical experiments show that our algorithm dominates the simulated annealing algorithm in accuracy of solutions and speed on both uniform and geometric instances. In particular, our tabu search implementation works much better than the simulated annealing algorithm on structured (geometric) instances. We also investigate how to tune up our implementation and to optimize the various parameters via extensive numerical experiments.

収録刊行物

被引用文献 (10)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ