| ■論文No. |
IS24013 |
| ■ページ数 |
6ページ |
■発行日
|
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) |
| ■価格 |
会員 ¥220 一般 ¥330 |
| ■書籍種類 |
研究会(論文単位) |
| ■グループ名 |
【C】電子・情報・システム部門 情報システム研究会 |
| ■本誌 |
2024年6月6日-2024年6月7日情報システム研究会
|
| ■本誌掲載ページ |
1-6ページ |
| ■原稿種別 |
日本語 |
| ■電子版へのリンク |
|
| ■キーワード |
次数制約付き最小スパニング木|次数制約|発見的解法|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. |
| ■版 型 |
A4 |
| ■PDFファイルサイズ |
985Kバイト |
