ダイナミックプログラミングによる最適系列グラフ分割問題の計算量
スポンサーリンク
概要
- 論文の詳細を見る
Optimal sequential partitions of graphs is finding a minimum cost partition of the nodes of a graph into subsets of a given size, subject to the constraint that the sequence of the nodes may not be changed, that is, that the nodes in a subset must heve consecutive numbers. We discuss some important point's improvements of Kernighan's dynamic programing algorithm for the problem, and the running time of the procedure is proportional to the number of edges in the graph. We present of an estimation about theoretical time complexity and compare it with numerical computation.
- 北海道情報大学の論文