{"created":"2023-05-15T11:58:56.231477+00:00","id":5155,"links":{},"metadata":{"_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":["15: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 < 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.","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","filename":"waac_2014.pdf","filesize":[{"value":"142.6 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","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"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-09-05"},"publish_date":"2017-09-05","publish_status":"0","recid":"5155","relation_version_is_last":true,"title":["Exact Algorithms for B-Bandwidth Problem with Restricted B"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-10-25T08:44:23.091605+00:00"}