WEKO3
-
RootNode
アイテム
Exact Algorithms for B-Bandwidth Problem with Restricted B
http://hdl.handle.net/10228/00006367
http://hdl.handle.net/10228/00006367aa1736f9-336f-48eb-b788-5abfd766a995
名前 / ファイル | ライセンス | アクション |
---|---|---|
waac_2014.pdf (142.6 kB)
|
|
Item type | 会議発表論文 = Conference Paper(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2017-09-05 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||||
資源タイプ | conference paper | |||||||||||
タイトル | ||||||||||||
タイトル | Exact Algorithms for B-Bandwidth Problem with Restricted B | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
Yukumoto, Hiroshi
× Yukumoto, Hiroshi× 斎藤, 寿樹
WEKO
22890
× Yamaguchi, Kazuaki× Masuda, Sumio |
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | 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. | |||||||||||
備考 | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | The 17th Korea-Japan Joint Workshop on Algorithms and Computation, July 13-15, 2014, Okinawa, Japan | |||||||||||
書誌情報 |
Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation 巻 2014, p. 44-49, 発行日 2014-07-13 |
|||||||||||
出版社 | ||||||||||||
出版者 | WAAC | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | VoR | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
研究者情報 | ||||||||||||
表示名 | https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html | |||||||||||
URL | https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html | |||||||||||
論文ID(連携) | ||||||||||||
値 | 10308202 | |||||||||||
連携ID | ||||||||||||
値 | 6299 |