ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
発行・発表の年月	1995/06
形態種別	論文
査読	査読あり
標題	NP‐completeness of interval graph completion from a path graph
執筆形態	共著・編著（代表編著を除く）
掲載誌名	Electronics and Communications in Japan (Part III: Fundamental Electronic Science)
掲載区分	国内
巻・号・頁	78(6),95-102頁
総ページ数	8
著者・共著者	Kazuaki Yamaguchi,Toshiro Araki,Toshinobu Kashiwabara
概要	Given a set of paths on a tree, the graph with vertices corresponding to the paths, where the corresponding vertices are connected by an edge when two paths intersect, is called the path graph. Given a set A of finite intervals on a straight line, the graph with vertices corresponding to the intervals belonging to A, where an edge is provided when two intervals intersect, is called the interval graph. In this paper, it is shown that the problem to decide whether or not a given path graph can be converted to an interval graph by adding K or less edges is NP‐complete. Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company
DOI	10.1002/ecjc.4430780610
ISSN	1042-0967/1520-6440