ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	1994/09/25
形態種別	国内学会誌（First author）
査読	査読あり
標題	パスグラフから区間グラフへの最小辺付加による変換のNP完全性
執筆形態	共著・編著（代表編著を除く）
掲載誌名	電子情報通信学会論文誌. A, 基礎・境界
出版社・発行元	一般社団法人電子情報通信学会
巻・号・頁	77(9),1269-1275頁
担当区分	筆頭著者
著者・共著者	山口 一章,荒木 俊郎,柏原 敏伸
概要	一つの木の上の道の集合が与えられたとき,道に対応して頂点をもち,二つの道が交わるとき対応する頂点が辺で結ばれているようなグラフをパスグラフと呼ぶ.直線上の有限個の区間の集合Aが与えられたとき,Aに属する区間を頂点とし二つの区間が交わるとき間に辺を持つようなグラフを区間グラフと呼ぶ.本研究では,パスグラフにK本以下の本数の辺を付加して区間グラフに変換することができるか否かを判定する問題がNP完全であることを証明する.
ISSN	0913-5707
NAID	110003313177
PermalinkURL	http://id.ndl.go.jp/bib/3888241