次数制約付き最小スパニング木問題に対する発見的解法の性能評価

カテゴリ: 研究会(論文単位)

論文No: IS24013

グループ名: 【C】電子・情報・システム部門 情報システム研究会

発行日: 2024/06/03

タイトル(英語): Evaluating heuristic algorithms for extracting the degree constrained minimum spanning tree

著者名: 大林 啓人(近畿大学),山内 雅弘(近畿大学),高藤 大介(周南公立大学)

著者名(英語): Hiroto Obayashi(Kindai University),Masahiro Yamauchi(Kindai University),Daisuke Takafuji(Shunan University)

キーワード: 次数制約付き最小スパニング木|次数制約|発見的解法|Degree constrained minimum spanning trees|Vertex degree constraint|Heuristic algorithm

要約(日本語): 次数制約付き最小スパニング木問題に対する発見的解法を提案した。比較対象として、既存の近似解法およびラグランジェ緩和法と劣勾配法で得られた下界値を用いた最適解法も実装した。計算機実験による比較評価を報告する。

要約(英語): We propose a heuristic algorithm for extracting the degree constrained minimum spanning tree. Also, we implement a branch and bound algorithm using lower bounds obtained by Lagrangian relaxation and Subgradient Method. We evaluate performance of our algorithm through the results of computing experiment.

本誌: 2024年6月6日-2024年6月7日情報システム研究会

本誌掲載ページ: 1-6 p

原稿種別: 日本語

PDFファイルサイズ: 985 Kバイト