2つのグラフの共通st順序付けのNP完全性
スポンサーリンク
概要
- 論文の詳細を見る
st順序付けとは,2連結グラフG(V,E)と辺st(s,tεV)が与えられたとき,sの番号が1,tの番号が|V|とし,他の全ての頂点は自分より小さな番号を持つ頂点と大きな番号を持つ頂点とに隣接しているような順序付けのことである.平面グラフとは,どの辺も交差しないように平面上に描くことが可能なグラフである.本稿では,共通の頂点集合を持つ2つの平面グラフのいずれに対してもst順序付けとなるような頂点への順序付けを与えるという問題がNP完全であることを示す.
- 一般社団法人情報処理学会の論文
- 1995-03-17
著者
関連論文
- 2つのグラフの共通st順序付けのNP完全性
- 妨害の下での最短経路問題
- パスグラフから区間グラフへの最小辺付加による変換の NP 完全性
- パスグラフから区間グラフへの最小辺付加による変換のNP完全性
- 平面グラフの最大重み窓問題