ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	英語
発行・発表の年月	2014/07
形態種別	外国学会誌（その他）
査読	査読あり
標題	Exact Algorithms for B-Bandwidth Problem with Restricted B
執筆形態	共著・編著（代表編著を除く）
掲載誌名	In Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation
出版社・発行元	WAAC
巻・号・頁	(2014),pp.44-49
著者・共著者	Hiroshi Yukumoto,SAITOH TOSHIKI,YAMAGUCHI KAZUAKI,MASUDA SUMIO
概要	The B-BANDWIDTH problem is a decision problem whether the bandwidth of a given graph is smaller than B, and it is NP-complete even if the graph is a small graph class of trees. Cygan and Pilipczuk proposed exponential time and space algorithms for B-BANDWIDTH with n/3 ≤ B where n is the number of vertices. In this paper, we propose two algorithms for the B-BANDWIDTH problem with n/4 ≤ B < n/3. These algorithms are extension of Cygan and Pilipczuk algorithms with restricted B. One of the algorithms takes O∗(4.5n) time and O∗(1.5n) space when n/4 ≤ B < n / 2 log2 1.5, and the other takes O∗(4.77n) time and O∗(1.59n) space when n / 2 log2 1.5 ≤ B < n/3. Our algorithms are fastest O∗(2n) space algorithms for n/4 ≤B < n/3. The 17th Korea-Japan Joint Workshop on Algorithms and Computation, July 13-15, 2014, Okinawa, Japan
NAID	120006665016
PermalinkURL	http://hdl.handle.net/10228/00006367