区間グラフの認識アルゴリズムについて

概要

論文の詳細を見る
区間グラフの認識アルゴリズムの初期のものは、少なくともO(n^3)時間を必要とした。線形アルゴリズムとして最初のものは、BoothとLeuker [JCSS,13,1976]により開発された。しかしそのアルゴリズムはPQ-treeという特殊なデータ構造を用いていたため、非常に複雑だった。そこでKorteとMoring[SIAM J.Comput.,18:68-81,1989]は、その複雑さを緩和するために、modified PQ-treeと呼ばれる、より柔軟性のあるPQ-treeを用いたアルゴリズムを開発した。Simon[LNCS 553,289-308,1991]によって開発された認識アルゴリズムは、辞書式順序幅優先探索(lexBFS)を4回繰り返すことで、PQ-treeを用いずに実現されている。この論文では、その認識アルゴリズムが間違いであることを示すとともに、lexBFSを行う回数を増やしても区間グラフを正しく認識することはできないことを証明する。
社団法人電子情報通信学会の論文
1997-04-25