ダイナミックプログラミングによる最適系列グラフ分割問題の計算量

書誌事項

タイトル別名
  • Complexity of Optimal Sequential Partitions of Graphs by Dynamic Programming

この論文をさがす

説明

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.

収録刊行物

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

  • CRID
    1573950401714076800
  • NII論文ID
    110004688314
  • NII書誌ID
    AN1017367X
  • ISSN
    09156658
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ