分枝限定法による系列グラフ分割問題の高速化と拡張

• Item type: SIG Technical Reports(1)
• 公開日: 1991-05-29
• タイトル: 分枝限定法による系列グラフ分割問題の高速化と拡張
• タイトル / 言語: en
• タイトル: An Improved Branch and Bound Algorithm for Sequential Partitions of Graphs and Related Problems
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道情報大学
• 著者所属: 北海道大学
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Hokkaido Information University
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Hokkaido University
• 著者名: 加地, 太一; 大内, 東
• 著者名(英): Taichi, Kaji; Azuma, Ohuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 頂点が連続的な番号を保持し、始点が初期番号、終点が最終番号となり、両端点が異なるグラフを系列グラフG（，）と呼ぶ。本論文における最適系列グラフ分割は系列グラフに対して、各頂点に与えられた重みの総和がブロックサイズP（>）以下であり、かつ、部分集合の頂点番号が連続的に保持される条件のもとで、カットされる辺のコストの和が最小となるよう分割する問題である。この問題に対して著者等はこれまでに開発したBranch?and?Bound法（）を用いた手法に対して、新たな改良改善を試み、また、その効率の評価、および計算量を算出する。さらに新しい問題の拡張を試みる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Optimal sequential partitions of graphs is to find a minimum cost partition of the nodes of a graph into subsets of a given size, subjecting to the constraint that the sequence of the nodes may not be changed, that is, that the nodes in a subset must be consecutive numbers. An improved Branch and Bound algorithm for the problem is proposed and its time complexity is discussed. Some varieties of the problems are also considered.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1991, 号 48(1991-AL-021), p. 1-8, 発行日 1991-05-29
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会