部分グラフ検出問題の時間計算量の下限

荒井 真成  山下 雅史  平田 富夫  茨木 俊秀  本多 波雄  

誌名
電子情報通信学会論文誌 D   Vol.J68-D   No.10   pp.1735-1743
発行日: 1985/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


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




あらまし: 
本論文では,あるグラフ問題のクラスに対し,代数決定木に基づく計算モデル上で時間計算量の自明でない下限を導出する.すなわち,πをグラフ上のある性質としたとき,枝実数重みつき完全無向グラフの中に,πを満足し枝の重みの総和が1に等しい部分グラフが存在するか?という問題を考える.最初に,πが同型に関する閉包性と次数制約条件を満足するとの前提の下で,下限Ωn3logn)を証明する.ただし,nはグラフの節点数である.中山らはπが連結成分依存かつ部分グラフに関し遺伝的である場合に対し,時間計算量の下限Ωn3logn)を示しているが,本結果はこの場合を含むものである.次に,次数制約条件を満足しない性質の例としてπがクリークである場合を考慮し,Ωn3)の下限を導く.