{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T05:17:44Z","timestamp":1775798264371,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p>\n            Driven by applications in graph analytics, the problem of efficiently computing all\n            <jats:italic>k<\/jats:italic>\n            -edge connected components (\n            <jats:italic>k<\/jats:italic>\n            -ECCs) of a graph\n            <jats:italic>G<\/jats:italic>\n            for\n            <jats:italic>a user-given k<\/jats:italic>\n            has been extensively and well studied. It is known that the\n            <jats:italic>k<\/jats:italic>\n            -ECCs of\n            <jats:italic>G<\/jats:italic>\n            for\n            <jats:italic>all possible values<\/jats:italic>\n            of\n            <jats:italic>k<\/jats:italic>\n            form a hierarchical structure. In this paper, we study the problem of efficiently constructing the hierarchy tree for\n            <jats:italic>G<\/jats:italic>\n            which compactly encodes the\n            <jats:italic>k<\/jats:italic>\n            -ECCs for all possible\n            <jats:italic>k<\/jats:italic>\n            values in space linear to the number of vertices\n            <jats:italic>n.<\/jats:italic>\n            All existing approaches construct the hierarchy tree in\n            <jats:italic>O<\/jats:italic>\n            (\u03b4(\n            <jats:italic>G<\/jats:italic>\n            ) \u00d7 T\n            <jats:sub>KECC<\/jats:sub>\n            <jats:sup>\n              (\n              <jats:italic>G<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) time, where \u03b4(\n            <jats:italic>G<\/jats:italic>\n            ) is the degeneracy of\n            <jats:italic>G<\/jats:italic>\n            and T\n            <jats:sub>KECC<\/jats:sub>\n            <jats:sup>\n              (\n              <jats:italic>G<\/jats:italic>\n              )\n            <\/jats:sup>\n            is the time complexity of computing all\n            <jats:italic>k<\/jats:italic>\n            -ECCs of\n            <jats:italic>G<\/jats:italic>\n            for a specific\n            <jats:italic>k<\/jats:italic>\n            value. To improve the time complexity, we propose a divide-and-conquer approach running in\n            <jats:italic>O<\/jats:italic>\n            ((log \u03b4(\n            <jats:italic>G<\/jats:italic>\n            )) \u00d7 T\n            <jats:sub>KECC<\/jats:sub>\n            <jats:sup>\n              (\n              <jats:italic>G<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) time, which is optimal up to a logarithmic factor. However, a straightforward implementation of our algorithm would result in a space complexity of\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            ) log \u03b4(\n            <jats:italic>G<\/jats:italic>\n            )). As main memory also becomes a scarce resource when processing large-scale graphs, we further propose techniques to optimize the space complexity to 2\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03b4(\n            <jats:italic>G<\/jats:italic>\n            )), where\n            <jats:italic>m<\/jats:italic>\n            is the number of edges in\n            <jats:italic>G.<\/jats:italic>\n            Extensive experiments on large real graphs and synthetic graphs demonstrate that our approach outperforms the state-of-the-art approaches by up to 28 times in terms of running time, and by up to 8 times in terms of main memory usage. As a by-product, we also improve the space complexity of computing all\n            <jats:italic>k<\/jats:italic>\n            -ECCs for a specific\n            <jats:italic>k<\/jats:italic>\n            to 2\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.14778\/3514061.3514063","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:26:10Z","timestamp":1655936770000},"page":"1146-1158","source":"Crossref","is-referenced-by-count":8,"title":["A near-optimal approach to edge connectivity-based hierarchical graph decomposition"],"prefix":"10.14778","volume":"15","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"The University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyi","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. full version: https:\/\/lijunchang.github.io\/pdf\/2022-ecd-tr.pdf.  [n.d.]. full version: https:\/\/lijunchang.github.io\/pdf\/2022-ecd-tr.pdf."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687725"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775227"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505751"},{"key":"e_1_2_1_5_1","volume-title":"Karger","author":"Bencz\u00far Andr\u00e1s A.","year":"2002","unstructured":"Andr\u00e1s A. Bencz\u00far and David R . Karger . 2002 . Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. CoRR cs.DS\/0207078 (2002). Andr\u00e1s A. Bencz\u00far and David R. Karger. 2002. Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. CoRR cs.DS\/0207078 (2002)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746486"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380033"},{"key":"e_1_2_1_9_1","series-title":"Springer Series in the Data Sciences","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 Series in the Data Sciences . Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465323"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_12_1","volume-title":"Proc. of AISTATS'18","author":"Cheng Dehua","year":"2018","unstructured":"Dehua Cheng , Natali Ruchansky , and Yan Liu . 2018 . Matrix completability analysis via graph k-connectivity . In Proc. of AISTATS'18 . 395--403. Dehua Cheng, Natali Ruchansky, and Yan Liu. 2018. Matrix completability analysis via graph k-connectivity. In Proc. of AISTATS'18. 395--403."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_15_1","volume-title":"Leiserson","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , and Charles E . Leiserson . 2001 . Introduction to Algorithms. McGraw-Hill Higher Education . Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. Introduction to Algorithms. McGraw-Hill Higher Education."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_18_1","volume-title":"Algorithmic Graph Theory","author":"Gibbons Alan","unstructured":"Alan Gibbons . 1985. Algorithmic Graph Theory . Cambridge University Press . Alan Gibbons. 1985. Algorithmic Graph Theory. Cambridge University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2098881"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_22_1","volume-title":"Proc. of SODA '13","author":"Kelner Jonathan A.","year":"2013","unstructured":"Jonathan A. Kelner , Yin Tat Lee , Lorenzo Orecchia , and Aaron Sidford . 2013 . An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations . In Proc. of SODA '13 . Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2013. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. In Proc. of SODA '13."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACIFICVIS.2017.8031574"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0109-y"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2006.76"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_2_1_31_1","unstructured":"Manuel Sorge and etal 2013. The graph parameter hierarchy.  Manuel Sorge and et al. 2013. The graph parameter hierarchy."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00014"},{"key":"e_1_2_1_34_1","volume-title":"White and Frank Harary","author":"Douglas","year":"2001","unstructured":"Douglas R. White and Frank Harary . 2001 . The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology 31 (2001). Douglas R. White and Frank Harary. 2001. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology 31 (2001)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081908"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457407"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0451-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247652"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3514061.3514063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:21:13Z","timestamp":1672219273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3514061.3514063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.14778\/3514061.3514063"],"URL":"https:\/\/doi.org\/10.14778\/3514061.3514063","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,2]]}}}