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)
|
|
| 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 | ||||||||||||||
| 論文ID（連携） | ||||||||||||||
| 10308202 | ||||||||||||||
| 連携ID | ||||||||||||||
| 6299 | ||||||||||||||
