ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	1995/03/17
形態種別	国内学会誌（その他）
標題	2つのグラフの共通st順序付けのNP完全性
執筆形態	共著・編著（代表編著を除く）
掲載誌名	情報処理学会研究報告アルゴリズム（AL）
出版社・発行元	一般社団法人情報処理学会
巻・号・頁	1995(32),53-60頁
担当区分	筆頭著者
著者・共著者	山口 一章,原田 俊彦
概要	st順序付けとは，2連結グラフG（，）と辺st（，t∈）が与えられたとき，sの番号が1，tの番号が│V│とし，他の全ての頂点は自分より小さな番号を持つ頂点と大きな番号を持つ頂点とに隣接しているような順序付けのことである．平面グラフとは，どの辺も交差しないように平面上に描くことが可能なグラフである．本稿では，共通の頂点集合を持つ2つの平面グラフのいずれに対してもst順序付けとなるような頂点への川旬宇付けを与えるという問題がNP完全であることを示す．
ISSN	0919-6072
NAID	110002812288
PermalinkURL	http://id.nii.ac.jp/1001/00032362/