WEKO3
アイテム
{"_buckets": {"deposit": "6aa3d017-71ac-40cf-aca9-c03bb5ec9280"}, "_deposit": {"created_by": 3, "id": "5155", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "5155"}, "status": "published"}, "_oai": {"id": "oai:kyutech.repo.nii.ac.jp:00005155", "sets": ["20"]}, "author_link": ["20675", "20676", "20673", "22890"], "item_23_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2014-07-13", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "49", "bibliographicPageStart": "44", "bibliographicVolumeNumber": "2014", "bibliographic_titles": [{"bibliographic_title": "Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation "}]}]}, "item_23_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "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 \u003c 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 \u003c 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 \u003c n/3. Our algorithms are fastest O∗(2n) space algorithms for n/4 ≤B \u003c n/3.", "subitem_description_type": "Abstract"}]}, "item_23_description_5": {"attribute_name": "内容記述", "attribute_value_mlt": [{"subitem_description": "The 17th Korea-Japan Joint Workshop on Algorithms and Computation, July 13-15, 2014, Okinawa, Japan", "subitem_description_type": "Other"}]}, "item_23_description_60": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"subitem_description": "Conference Paper", "subitem_description_type": "Other"}]}, "item_23_link_61": {"attribute_name": "研究者情報", "attribute_value_mlt": [{"subitem_link_text": "https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html", "subitem_link_url": "https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html"}]}, "item_23_publisher_7": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "WAAC"}]}, "item_23_select_59": {"attribute_name": "査読の有無", "attribute_value_mlt": [{"subitem_select_item": "yes"}]}, "item_23_text_28": {"attribute_name": "論文ID(連携)", "attribute_value_mlt": [{"subitem_text_value": "10308202"}]}, "item_23_text_37": {"attribute_name": "著者所属", "attribute_value_mlt": [{"subitem_text_value": "Graduate School of Informatics, Kyoto University"}, {"subitem_text_value": "Graduate School of Engineering, Kobe University"}, {"subitem_text_value": "Graduate School of Engineering, Kobe University"}, {"subitem_text_value": "Graduate School of Engineering, Kobe University"}]}, "item_23_text_62": {"attribute_name": "連携ID", "attribute_value_mlt": [{"subitem_text_value": "6299"}]}, "item_23_version_type_58": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Yukumoto, Hiroshi"}], "nameIdentifiers": [{"nameIdentifier": "20673", "nameIdentifierScheme": "WEKO"}]}, {"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Saitoh, Toshiki", "creatorNameLang": "en"}, {"creatorName": "斎藤, 寿樹", "creatorNameLang": "ja"}, {"creatorName": "サイトウ, トシキ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "Saitoh", "familyNameLang": "en"}, {"familyName": "斎藤", "familyNameLang": "ja"}, {"familyName": "サイトウ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Toshiki", "givenNameLang": "en"}, {"givenName": "寿樹", "givenNameLang": "ja"}, {"givenName": "トシキ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "22890", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "00590390", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000000590390"}, {"nameIdentifier": "29567479100", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=29567479100"}, {"nameIdentifier": "100000980", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html"}]}, {"creatorNames": [{"creatorName": "Yamaguchi, Kazuaki"}], "nameIdentifiers": [{"nameIdentifier": "20675", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Masuda, Sumio"}], "nameIdentifiers": [{"nameIdentifier": "20676", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-09-05"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "waac_2014.pdf", "filesize": [{"value": "142.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 142600.0, "url": {"label": "waac_2014.pdf", "url": "https://kyutech.repo.nii.ac.jp/record/5155/files/waac_2014.pdf"}, "version_id": "d01e2583-bb9d-42de-b74c-0a474ee9f220"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "conference paper", "resourceuri": "http://purl.org/coar/resource_type/c_5794"}]}, "item_title": "Exact Algorithms for B-Bandwidth Problem with Restricted B", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Exact Algorithms for B-Bandwidth Problem with Restricted B"}]}, "item_type_id": "23", "owner": "3", "path": ["20"], "permalink_uri": "http://hdl.handle.net/10228/00006367", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-09-05"}, "publish_date": "2017-09-05", "publish_status": "0", "recid": "5155", "relation": {}, "relation_version_is_last": true, "title": ["Exact Algorithms for B-Bandwidth Problem with Restricted B"], "weko_shared_id": 3}
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 | ||||||||||||
著者所属 | ||||||||||||
Graduate School of Informatics, Kyoto University | ||||||||||||
著者所属 | ||||||||||||
Graduate School of Engineering, Kobe University | ||||||||||||
著者所属 | ||||||||||||
Graduate School of Engineering, Kobe University | ||||||||||||
著者所属 | ||||||||||||
Graduate School of Engineering, Kobe University | ||||||||||||
資料タイプ | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | Conference Paper |