An Implementation of an Interval-Edge-Deletion Algorithm Using Path-decomposition
Bibliographic Information
- Other Title
-
- パス分解を用いた区間辺削除アルゴリズムの実装
Abstract
<p>区間グラフは数直線上の区間の集合を表現に持つグラフで,スケジューリングやバイオインフォマティクスへの応用がある.本稿では,一般のグラフからいくつか辺を削除して区間グラフを生成することを考える.区間辺削除問題はこのとき削除する辺の本数を最小化する問題で,NP困難であることが知られている.近年,区間辺削除問題に対するパス分解と呼ばれるグラフのパス構造に基づいた動的計画法によるアルゴリズムが提案された.本論文では,そのアルゴリズムに対する効率的な実装方法を示すとともに,アルゴリズムの効率性を計算機実験により示す.</p>
Journal
-
- Record of Joint Conference of Electrical and Electronics Engineers in Kyushu
-
Record of Joint Conference of Electrical and Electronics Engineers in Kyushu 2021 (0), 78-79, 2021-09-17
Committee of Joint Conference of Electrical, Electronics and Information Engineers in Kyushu
- Tweet
Details 詳細情報について
-
- CRID
- 1390854882639062784
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
-
- Abstract License Flag
- Disallowed