グラフ変形操作の効率的アルゴリズム

千葉 則茂  西関 隆夫  斎藤 伸自  

誌名
電子情報通信学会論文誌 D   Vol.J64-D   No.10   pp.934-939
発行日: 1981/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(470.3KB)>>
論文を購入




あらまし: 
グラフのアルゴリズムには種々の“グラフの変形操作”が用いられる.その最も基本的な操作として“点の除去”,“点の短絡”,“枝の開放除去”,“枝の短絡除去”がある.グラフの変形操作の大部分はこれらの基本操作の幾つかを組み合せたものとみなすことができる.又,アルゴリズム中には,与えられた2点間に枝があるかないかを問う枝存在判定が何回も現れることが多い.本論文では,グラフを表現する種々のデータ構造に対して,変形操作・枝判定に必要な計算時間について考察をする.特に,隣接行列と隣接リストの両方を用いるか,あるいは隣接リストにAVL-木を用いれば,変形操作・枝存在判定の任意の系列をOmlogn)時間で実行できるアルゴリズムがあることを示す.ここで,nはグラフの点数,mは枝数である.このアルゴリズムは広い応用を持っており,その幾つかの例も与えた.例えば,直並列グラフであるかどうかの判定,最小木問題,平面グラフの5-彩色などである.