可約なフローグラフの被覆道を求める多項式時間のアルゴリズム

平田 富夫  丸岡 章  木村 正行  

誌名
電子情報通信学会論文誌 D   Vol.J62-D   No.6   pp.411-418
発行日: 1979/06/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
グラフGと整数kの対(Gk)に対して,Gのすべての節点を被覆する互いに素なk本の非サイクル道が存在するか否かを問う問題は被覆道集合問題と呼ばれるが,この問題はGを可約なフローグラフに限ってもNP完全であることが知られている.又,パラメータkを固定した場合も.この問題はNP完全である(k=1のとき,この問題はハミルトン道問題となる).本論文では,Gを可約なフローグラフに限った場合のハミルトン道問題に対し,時間計算量がOne)のアルゴリズムを与える.ここで,nはフローグラフの節点数,eは枝数である.更に,このアルゴリズムを拡張して,パラメータkを固定し,入力を可約なフローグラフに限った場合の被覆道集合問題に対し,時間計算量がOnke)のアルゴリズムを与える.