フローグラフの深さ問題について

平田 富夫  丸岡 章  木村 正行  

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


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




あらまし: 
フローグラフの1本の非サイクル道に含まれる逆向枝の最大個数を,そのフローグラフの深さという.繰返し法を用いてコード最適化を行う場合,フローグラフの深さを求める問題や,フローグラフの深さを最小にする深さ優先の極大木(DFST)を求める問題が重要となるが,一般のフローグラフの深さを求める問題がNP-完全であることと,可約なフローグラフの深さがOne)のステップ数で求められることが既に知られている.ここで,nはフローグラフの節点数,eは枝数である.本論文では,可約なフローグラフの部分クラスであるDチャートに対し,その深さを求めるOn)のアルゴリズムを与える.又,一般のフローグラフに対し,その深さを最小にするDFSTを求める問題がNP-完全であることを示す.更に,一般のフローグラフに対し,その深さを最大にするDFSTを求める問題もNP-完全であることを示す.