WEKO3
アイテム
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)
|
|
| アイテムタイプ | 会議発表論文 = 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 | |||||||||||
| 言語 | en | |||||||||||
| 言語 | ||||||||||||
| 言語 | 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 | |||||||||||
| 研究者情報 | ||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html | |||||||||||
| 論文ID（連携） | ||||||||||||
| 値 | 10308202 | |||||||||||
| 連携ID | ||||||||||||
| 値 | 6299 | |||||||||||
