Complexity of Optimal Sequential Partitions of Graphs by Dynamic Programming

  • KAJI Taichi
    Department of Information Science, Faculty of Business Administration and Information Science

Bibliographic Information

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

Search this article

Description

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.

Journal

Details 詳細情報について

  • CRID
    1573950401714076800
  • NII Article ID
    110004688314
  • NII Book ID
    AN1017367X
  • ISSN
    09156658
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top