ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	1993/05/27
形態種別	国内学会誌（その他）
標題	パスグラフから区間グラフへの最小辺付加による変換のNP完全性
執筆形態	共著・編著（代表編著を除く）
掲載誌名	電子情報通信学会技術研究報告. COMP, コンピュテーション
出版社・発行元	一般社団法人電子情報通信学会
巻・号・頁	93(81),15-20頁
担当区分	筆頭著者
著者・共著者	山口 一章,荒木 俊郎,柏原 敏伸
概要	1つの木の上の道の集合が与えられたとき,道に対応して頂点をもち,2つの道が交わるとき対応する頂点が辺で結ばれているようなグラフをパスグラフと呼ぶ.直線上の有限個の区間の集合Aが与えられたとき,Aに属する区間を頂点とし2つの区間が交わるとき間に辺を持つようなグラフを区間グラフと呼ぶ.本論文では,パスグラフにK本以下の本数の辺を付加して区間グラフに変換することができるか否かを判定する問題がNP完全であることを証明する.
NAID	110003191581