{"links":{},"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00240709","sets":["581:11492:11504"]},"path":["11504"],"owner":"44499","recid":"240709","title":["Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-11-15"},"_buckets":{"deposit":"b1aaf69f-f6b5-444f-a865-9973feec94f2"},"_deposit":{"id":"240709","pid":{"type":"depid","value":"240709","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs","author_link":["660815","660816","660817","660818","660813","660814"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs"},{"subitem_title":"Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文] enumeration algorithms, subgraph enumeration, support-closed connected induced subgraphs, protein-protein network, GWAS","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2024-11-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Kyoto University"},{"subitem_text_value":"Kyoto University"},{"subitem_text_value":"Kyoto University"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"Kyoto University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/240709/files/IPSJ-JNL6511001.pdf","label":"IPSJ-JNL6511001.pdf"},"date":[{"dateType":"Available","dateValue":"2026-11-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL6511001.pdf","filesize":[{"value":"956.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"6d693bdf-f362-469e-9daa-e67dd5da8393","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Daiki, Watanabe"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Takumi, Tada"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuya, Haraguchi"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Daiki, Watanabe","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Takumi, Tada","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuya, Haraguchi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_publisher_15":{"attribute_name":"公開者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Suppose that we are given a tuple (G,I,σ) of an undirected graph G=(V,E), an itemset I={1,2,...,q}, and a mapping σ:V → 2I. For S ⊆ V, let us denote Iσ(S):=∩v∈sσ(v). We say that S induces a support-closed connected subgraph if S is maximal with respect to the connectivity and the common itemset (i.e., the subgraph G[S] induced by S is connected and, for any v ∈ V ＼ S, G[S∪{v}] is disconnected or Iσ(S∪{v}) ⊊ Iσ(S)). Several algorithms have been developed for enumerating all support-closed connected induced subgraphs, where some of them are shown to be polynomial-amortized or polynomial-delay. However, a theoretical complexity bound does not necessarily represent the empirical performance of an algorithm. In this paper, we compare the empirical performance of four enumeration algorithms named COPINE (branch-and-bound), COOMA (dynamic programming), FT (family-tree) and BP (binary partition), respectively. We observe that, for random instances, COOMA is generally the fastest, followed by BP, and that these two algorithms are more robust to parameters of random instances than the other two. We then extend BP to a problem that arises from bacterial GWAS (Genome-Wide Association Studies) and observe that its implementation is much faster than an existing implementation of CALDERA, a previous algorithm.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.32(2024) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.32.894\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Suppose that we are given a tuple (G,I,σ) of an undirected graph G=(V,E), an itemset I={1,2,...,q}, and a mapping σ:V → 2I. For S ⊆ V, let us denote Iσ(S):=∩v∈sσ(v). We say that S induces a support-closed connected subgraph if S is maximal with respect to the connectivity and the common itemset (i.e., the subgraph G[S] induced by S is connected and, for any v ∈ V ＼ S, G[S∪{v}] is disconnected or Iσ(S∪{v}) ⊊ Iσ(S)). Several algorithms have been developed for enumerating all support-closed connected induced subgraphs, where some of them are shown to be polynomial-amortized or polynomial-delay. However, a theoretical complexity bound does not necessarily represent the empirical performance of an algorithm. In this paper, we compare the empirical performance of four enumeration algorithms named COPINE (branch-and-bound), COOMA (dynamic programming), FT (family-tree) and BP (binary partition), respectively. We observe that, for random instances, COOMA is generally the fastest, followed by BP, and that these two algorithms are more robust to parameters of random instances than the other two. We then extend BP to a problem that arises from bacterial GWAS (Genome-Wide Association Studies) and observe that its implementation is much faster than an existing implementation of CALDERA, a previous algorithm.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.32(2024) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.32.894\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2024-11-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"11","bibliographicVolumeNumber":"65"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:45:02.988949+00:00","updated":"2025-01-19T07:53:40.056841+00:00","id":240709}