辺の短絡除去あるいは辺の開放除去による直並列グラフの構成問題

渡辺 敏正  阿江 忠  中村 昭  

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


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




あらまし: 
辺の短絡除去(辺の開放除去)による直並列グラフの構成問題とは,与えられたグラフGから直並列グラフを構成するために短絡除去(開放除去)すべき最小辺数を求める問題であり,形式的には,Gと非負整数kに対して,Gからk本以下の辺を短絡除去(開放除去)することにより直並列グラフが構成できるか否かを決定する決定問題PSPECPSPED)と定義される,本論文は,
(1)PSPECPSPEDが共に非決定性チューリング機械により入力サイズに関する多項式時間で解けること.
(2)最大節点次数がたかだか4の平面グラフに対するスタイナー木(Steiner tree)問題がPSPEC及びPSPEDそれぞれに多項式変換可能である(polynomially transformable)こと.
を証明することにより,PSPECPSPEDいずれもがNP-完全であることを示すものである.