パス分解を用いた区間辺削除アルゴリズムの実装
書誌事項
- タイトル別名
-
- An Implementation of an Interval-Edge-Deletion Algorithm Using Path-decomposition
抄録
<p>区間グラフは数直線上の区間の集合を表現に持つグラフで，スケジューリングやバイオインフォマティクスへの応用がある．本稿では，一般のグラフからいくつか辺を削除して区間グラフを生成することを考える．区間辺削除問題はこのとき削除する辺の本数を最小化する問題で，NP困難であることが知られている．近年，区間辺削除問題に対するパス分解と呼ばれるグラフのパス構造に基づいた動的計画法によるアルゴリズムが提案された．本論文では，そのアルゴリズムに対する効率的な実装方法を示すとともに，アルゴリズムの効率性を計算機実験により示す．</p>
収録刊行物
-
- 電気関係学会九州支部連合大会講演論文集
-
電気関係学会九州支部連合大会講演論文集 2021 (0), 78-79, 2021-09-17
電気・情報関係学会九州支部連合大会委員会