{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:02:28Z","timestamp":1774983748528,"version":"3.50.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62102117"],"award-info":[{"award-number":["62102117"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    The\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than\n                    <jats:italic toggle=\"yes\">n-s<\/jats:italic>\n                    vertices are removed, where\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    is the number of vertices inside. Finding the largest\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of\n                    <jats:italic toggle=\"yes\">O*<\/jats:italic>\n                    (2\n                    <jats:italic toggle=\"yes\">\n                      <jats:sup>n<\/jats:sup>\n                    <\/jats:italic>\n                    ), where\n                    <jats:italic toggle=\"yes\">O*<\/jats:italic>\n                    suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to\n                    <jats:italic toggle=\"yes\">O*<\/jats:italic>\n                    (\u03bb\n                    <jats:italic toggle=\"yes\">\n                      <jats:sup>n<\/jats:sup>\n                      <jats:sub>s<\/jats:sub>\n                    <\/jats:italic>\n                    ) where \u03bb\n                    <jats:italic toggle=\"yes\">\n                      <jats:sub>s<\/jats:sub>\n                    <\/jats:italic>\n                    is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.\n                  <\/jats:p>","DOI":"10.1145\/3709687","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Maximum\n                    <i>s<\/i>\n                    -Bundle Search via Local Vertex Connectivity"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0759-2948","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2030-957X","authenticated-orcid":false,"given":"Hejiao","family":"Huang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1153-2902","authenticated-orcid":false,"given":"Kaiqiang","family":"Yu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5786-6938","authenticated-orcid":false,"given":"Shengxin","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Technical Report. https:\/\/github.com\/liubufan1998\/Maximum-sbundle-computation\/blob\/master\/Technical%20Report.pdf."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690506"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.001"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_2_5_1","volume-title":"CoRR cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matja\u017e Zaver\u0161nik. 2003. An O(m) algorithm for cores decomposition of networks. CoRR cs.DS\/0310049 (2003)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3325859"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617313"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746486"},{"key":"e_1_2_2_10_1","volume-title":"Cohesive Subgraph Computation over Large Sparse Graphs","author":"Chang Lijun","unstructured":"Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565817"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639318"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465323"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_2_17_1","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report 16 3.1 (2008)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677142"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526143"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588931"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_2_22_1","series-title":"SIAM journal on computing 4, 4","volume-title":"Network flow and testing graph connectivity","author":"Even Shimon","year":"1975","unstructured":"Shimon Even and R Endre Tarjan. 1975. Network flow and testing graph connectivity. SIAM journal on computing 4, 4 (1975), 507--518."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457538"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/201"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21257"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). 2570--2583","author":"Gao Shuohao","year":"2024","unstructured":"Shuohao Gao, Kaiqiang Yu, Shengxin Liu, Cheng Long, and Zelong Qiu. 2024. On searching maximum directed (k, l)-plex. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 2570--2583."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.09.039"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00188"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.11.043"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01874-9"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/623"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/233"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00712-2"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-019-00725-6"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55699-4_25"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00233"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00072"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483940"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90071-0"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2016.10.005"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.05.041"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2006.12.014"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639262"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/627"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00014"},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). 74--85","author":"Xiang Jingen","year":"2013","unstructured":"Jingen Xiang, Cong Guo, and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using MapReduce. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 74--85."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10655"},{"key":"e_1_2_2_56_1","volume-title":"Efficient and effective algorithms for densest subgraph discovery and maintenance. The VLDB Journal","author":"Xu Yichen","year":"2024","unstructured":"Yichen Xu, Chenhao Ma, Yixiang Fang, and Zhifeng Bao. 2024. Efficient and effective algorithms for densest subgraph discovery and maintenance. The VLDB Journal (2024)."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617331"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588729"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.03.009"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0451-4"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150506"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247652"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17477"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.05.001"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709687","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:22:39Z","timestamp":1774981359000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709687"],"URL":"https:\/\/doi.org\/10.1145\/3709687","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}