WEKO3
アイテム
{"_buckets": {"deposit": "67a03c87-ca07-4e43-b87d-b9318c48a8e1"}, "_deposit": {"created_by": 3, "id": "7781", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "7781"}, "status": "published"}, "_oai": {"id": "oai:kyutech.repo.nii.ac.jp:00007781", "sets": ["9"]}, "author_link": ["6037", "34129", "34131", "34128", "34132"], "item_21_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2013-01-10", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "99", "bibliographicPageStart": "88", "bibliographicVolumeNumber": "27", "bibliographic_titles": [{"bibliographic_title": "Journal of Combinatorial Optimization"}]}]}, "item_21_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The paper studies a generalization of the INDEPENDENT SET problem (IS for short). A distance-d independent set for an integer d≥2 in an unweighted graph G=(V,E) is a subset S⊆V of vertices such that for any pair of vertices u,v∈S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the DISTANCE-d INDEPENDENT SET problem (D d IS for short) is to decide whether G contains a distance-d independent set S such that |S|≥k. D2IS is identical to the original IS. Thus D2IS is NP-complete even for planar graphs, but it is in P for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance-d independent set: (1) We first prove that for any ε\u003e0 and any fixed integer d≥3, it is NP-hard to approximate MaxD d IS to within a factor of n1/2−ε for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is W[1]-hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP-complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP-complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1]-hardness of ParaD d IS(k) on chordal graphs for any odd d≥3.", "subitem_description_type": "Abstract"}]}, "item_21_description_60": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"subitem_description": "Journal Article", "subitem_description_type": "Other"}]}, "item_21_full_name_3": {"attribute_name": "著者別名", "attribute_value_mlt": [{"nameIdentifiers": [{"nameIdentifier": "34131", "nameIdentifierScheme": "WEKO"}], "names": [{"name": "Eto, H."}]}, {"nameIdentifiers": [{"nameIdentifier": "34132", "nameIdentifierScheme": "WEKO"}], "names": [{"name": "Guo, F."}]}, {"affiliations": [{"affiliationNames": [{"affiliationName": "", "lang": "ja"}], "nameIdentifiers": []}], "familyNames": [{"familyName": "Miyano", "familyNameLang": "en"}, {"familyName": "宮野", "familyNameLang": "ja"}, {"familyName": "ミヤノ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Eiji", "givenNameLang": "en"}, {"givenName": "英次", "givenNameLang": "ja"}, {"givenName": "エイジ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "6037", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10284548", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000010284548"}, {"nameIdentifier": "6603649200", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=6603649200"}, {"nameIdentifier": "0000-0002-4260-7818", "nameIdentifierScheme": "ORCiD", "nameIdentifierURI": "https://orcid.org/0000-0002-4260-7818"}, {"nameIdentifier": "233", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}], "names": [{"name": "Miyano, Eiji", "nameLang": "en"}, {"name": "宮野, 英次", "nameLang": "ja"}, {"name": "ミヤノ, エイジ", "nameLang": "ja-Kana"}]}]}, "item_21_link_62": {"attribute_name": "研究者情報", "attribute_value_mlt": [{"subitem_link_text": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html", "subitem_link_url": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]}, "item_21_publisher_7": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Springer"}]}, "item_21_relation_12": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isVersionOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1007/s10878-012-9594-4", "subitem_relation_type_select": "DOI"}}]}, "item_21_rights_13": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "Copyright (c) Springer Science+Business Media New York 2013. This is a post-peer-review, pre-copyedit version of an article published in Journal of Combinatorial Optimization. The final authenticated version is available online at: https://doi.org/10.1007/s10878-012-9594-4."}]}, "item_21_select_59": {"attribute_name": "査読の有無", "attribute_value_mlt": [{"subitem_select_item": "yes"}]}, "item_21_source_id_8": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1573-2886", "subitem_source_identifier_type": "ISSN"}, {"subitem_source_identifier": "1382-6905", "subitem_source_identifier_type": "ISSN"}]}, "item_21_text_28": {"attribute_name": "論文ID(連携)", "attribute_value_mlt": [{"subitem_text_value": "10347752"}]}, "item_21_text_36": {"attribute_name": "著者所属", "attribute_value_mlt": [{"subitem_text_value": "Kyushu Institute of Technology"}, {"subitem_text_value": "Kyushu Institute of Technology"}, {"subitem_text_value": "Kyushu Institute of Technology"}]}, "item_21_text_63": {"attribute_name": "連携ID", "attribute_value_mlt": [{"subitem_text_value": "10664"}]}, "item_21_version_type_58": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Eto, Hiroshi"}], "nameIdentifiers": [{"nameIdentifier": "34128", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Guo, Fengrui"}], "nameIdentifiers": [{"nameIdentifier": "34129", "nameIdentifierScheme": "WEKO"}]}, {"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Miyano, Eiji", "creatorNameLang": "en"}, {"creatorName": "宮野, 英次", "creatorNameLang": "ja"}, {"creatorName": "ミヤノ, エイジ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "Miyano", "familyNameLang": "en"}, {"familyName": "宮野", "familyNameLang": "ja"}, {"familyName": "ミヤノ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Eiji", "givenNameLang": "en"}, {"givenName": "英次", "givenNameLang": "ja"}, {"givenName": "エイジ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "6037", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10284548", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000010284548"}, {"nameIdentifier": "6603649200", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=6603649200"}, {"nameIdentifier": "0000-0002-4260-7818", "nameIdentifierScheme": "ORCiD", "nameIdentifierURI": "https://orcid.org/0000-0002-4260-7818"}, {"nameIdentifier": "233", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2022-10-03"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "10347752.pdf", "filesize": [{"value": "161.3 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 161300.0, "url": {"label": "10347752.pdf", "url": "https://kyutech.repo.nii.ac.jp/record/7781/files/10347752.pdf"}, "version_id": "d6f5a1ae-03e5-4cdb-9227-47ec92deab1f"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Distance-d independent set", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Bipartite graphs", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Chordal graphs", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Computational complexity", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Distance-d independent set problems for bipartite and chordal graphs", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Distance-d independent set problems for bipartite and chordal graphs"}]}, "item_type_id": "21", "owner": "3", "path": ["9"], "permalink_uri": "http://hdl.handle.net/10228/00008984", "pubdate": {"attribute_name": "公開日", "attribute_value": "2022-10-03"}, "publish_date": "2022-10-03", "publish_status": "0", "recid": "7781", "relation": {}, "relation_version_is_last": true, "title": ["Distance-d independent set problems for bipartite and chordal graphs"], "weko_shared_id": 3}
Distance-d independent set problems for bipartite and chordal graphs
http://hdl.handle.net/10228/00008984
http://hdl.handle.net/10228/00008984573bacba-6fdb-4861-852a-0ae39781f3f4
名前 / ファイル | ライセンス | アクション |
---|---|---|
10347752.pdf (161.3 kB)
|
|
Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2022-10-03 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
タイトル | ||||||||||||
タイトル | Distance-d independent set problems for bipartite and chordal graphs | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
Eto, Hiroshi
× Eto, Hiroshi× Guo, Fengrui× 宮野, 英次
WEKO
6037
|
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | The paper studies a generalization of the INDEPENDENT SET problem (IS for short). A distance-d independent set for an integer d≥2 in an unweighted graph G=(V,E) is a subset S⊆V of vertices such that for any pair of vertices u,v∈S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the DISTANCE-d INDEPENDENT SET problem (D d IS for short) is to decide whether G contains a distance-d independent set S such that |S|≥k. D2IS is identical to the original IS. Thus D2IS is NP-complete even for planar graphs, but it is in P for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance-d independent set: (1) We first prove that for any ε>0 and any fixed integer d≥3, it is NP-hard to approximate MaxD d IS to within a factor of n1/2−ε for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is W[1]-hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP-complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP-complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1]-hardness of ParaD d IS(k) on chordal graphs for any odd d≥3. | |||||||||||
書誌情報 |
Journal of Combinatorial Optimization 巻 27, p. 88-99, 発行日 2013-01-10 |
|||||||||||
出版社 | ||||||||||||
出版者 | Springer | |||||||||||
DOI | ||||||||||||
関連タイプ | isVersionOf | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | https://doi.org/10.1007/s10878-012-9594-4 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 1573-2886 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 1382-6905 | |||||||||||
著作権関連情報 | ||||||||||||
権利情報 | Copyright (c) Springer Science+Business Media New York 2013. This is a post-peer-review, pre-copyedit version of an article published in Journal of Combinatorial Optimization. The final authenticated version is available online at: https://doi.org/10.1007/s10878-012-9594-4. | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Distance-d independent set | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Bipartite graphs | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Chordal graphs | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Computational complexity | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | AM | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
研究者情報 | ||||||||||||
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | ||||||||||||
論文ID(連携) | ||||||||||||
10347752 | ||||||||||||
連携ID | ||||||||||||
10664 | ||||||||||||
資料タイプ | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | Journal Article | |||||||||||
著者別名 | ||||||||||||
姓名 | Eto, H. | |||||||||||
著者別名 | ||||||||||||
姓名 | Guo, F. | |||||||||||
著者別名 | ||||||||||||
姓名 | Miyano, Eiji | |||||||||||
言語 | en | |||||||||||
姓名 | 宮野, 英次 | |||||||||||
言語 | ja | |||||||||||
姓名 | ミヤノ, エイジ | |||||||||||
言語 | ja-Kana | |||||||||||
著者所属 | ||||||||||||
Kyushu Institute of Technology | ||||||||||||
著者所属 | ||||||||||||
Kyushu Institute of Technology | ||||||||||||
著者所属 | ||||||||||||
Kyushu Institute of Technology |