辺の短絡除去による平面グラフ化問題―最大節点次数がたかだか3の場合―

渡辺 敏正  阿江 忠  中村 昭  

誌名
電子情報通信学会論文誌 D   Vol.J64-D   No.3   pp.286-287
発行日: 1981/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 技術談話室
専門分野: 
キーワード: 


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




あらまし: 
最大節点次数がたかだか3のグラフから平面グラフを構成するために短絡除去すべき最小辺数を求める問題がNP-完全であることを示す.