講演抄録/キーワード |
講演名 |
2007-06-29 14:15
区間表現からMPQ-treeを効率よく構成するアルゴリズム ○斎藤寿樹・清見 礼・上原隆平(北陸先端大) COMP2007-24 |
抄録 |
(和) |
区間グラフは区間表現を持つグラフで、様々な応用があることが知られている.MPQ-treeは区間グラフを表現するデータ構造である.これは区間グラフ上の問題を解く上で有用なデータ構造である.本論文では区間グラフG=(V,E)の区間表現が与えられたとき、Gに対応するMPQ-treeを構築する単純なアルゴリズムを提案する.入力の区間表現の端点がソートされていたとき、このアルゴリズムはO(|V|)時間・領域で実行でき、理論的に計算量は最適である.さらに、このアルゴリズムは既存のアルゴリズムよりも実装が簡単である. |
(英) |
An MPQ-tree is an informative data structure for an interval graph. We propose a simple algorithm that constructs an MPQ-tree for an interval graph G=(V,E) given in the interval representation. If endpoints of the interval representation are already sorted, the algorithm runs in O(|V|) time and space, which is optimal from theoretical viewpoint. Further, our algorithm is much simpler than the previously known algorithms. |
キーワード |
(和) |
MPQ-tree / 区間グラフ / 区間表現 / / / / / |
(英) |
MPQ-tree / interval graph / interval representation / / / / / |
文献情報 |
信学技報, vol. 107, no. 127, COMP2007-24, pp. 49-54, 2007年6月. |
資料番号 |
COMP2007-24 |
発行日 |
2007-06-22 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-24 |