{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:26:18Z","timestamp":1752985578460,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["311451\/2016-0"],"award-info":[{"award-number":["311451\/2016-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00658-6","type":"journal-article","created":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T12:05:02Z","timestamp":1576325102000},"page":"1601-1615","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions"],"prefix":"10.1007","volume":"82","author":[{"given":"Charles","family":"Maske","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaime","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8916-3302","authenticated-orcid":false,"suffix":"Jr.","given":"Elias P.","family":"Duarte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,14]]},"reference":[{"key":"658_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity. Algorithmic Aspects of Graph Connectivity","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, Cambridge (2008)"},{"key":"658_CR2","doi-asserted-by":"crossref","unstructured":"Duarte\u00a0Jr, E., Santini, R., Cohen, J.: Delivering packets during the routing convergence latency interval through highly connected detours. In: 2004 International Conference on Dependable Systems and Networks, pp. 495\u2013504 (2004)","DOI":"10.1109\/DSN.2004.1311919"},{"key":"658_CR3","doi-asserted-by":"crossref","unstructured":"Engelberg, R., K\u00f6nemann, J., Leonardi, S., Naor, J.: Cut problems in graphs with a budget constraint. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006: theoretical informatics. Lecture notes in computer science, vol. 3887, pp. 435\u2013446. Berlin Heidelberg, Springer (2006)","DOI":"10.1007\/11682462_41"},{"issue":"1","key":"658_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"658_CR5","unstructured":"Mitrofanova, A., Farach-Colton, M., Mishra, B.: Efficient and robust prediction algorithms for protein complexes using Gomory\u2013Hu trees. In: Pacific Symposium on Biocomputing, pp. 215\u2013226 (2009)"},{"issue":"10","key":"658_CR6","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1002\/prot.22741","volume":"78","author":"N Tuncbag","year":"2010","unstructured":"Tuncbag, N., Salman, F.S., Keskin, O., Gursoy, A.: Analysis and network representation of hotspots in protein interfaces using minimum cut trees. Proteins Struct. Funct. Bioinform. 78(10), 2283\u20132294 (2010)","journal-title":"Proteins Struct. Funct. Bioinform."},{"key":"658_CR7","doi-asserted-by":"crossref","unstructured":"Kamath, K.Y., Caverlee, J.: Transient crowd discovery on the real-time social web. In: Proceedings of the 4th ACM International Conference on Web Search and Data Mining, WSDM \u201911, pp. 585\u2013594. ACM (2011)","DOI":"10.1145\/1935826.1935909"},{"key":"658_CR8","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Dwork, C., Kleinberg, J.: Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of the 16th International Conference on World Wide Web, WWW \u201907, pp. 181\u2013190. ACM (2007)","DOI":"10.1145\/1242572.1242598"},{"issue":"4","key":"658_CR9","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1016\/0360-8352(95)00022-S","volume":"28","author":"C-B Kim","year":"1995","unstructured":"Kim, C.-B., Foote, B.L., Pulat, P.: Cut-tree construction for facility layout. Comput. Ind. Eng. 28(4), 721\u2013730 (1995)","journal-title":"Comput. Ind. Eng."},{"key":"658_CR10","unstructured":"Jermaine, C.: Computing program modularizations using the k-cut method. In: Sixth Working Conference on Reverse Engineering, 1999. Proceedings. pp. 224\u2013234 (1999)"},{"key":"658_CR11","unstructured":"Saha, B., Mitra, P.: Dynamic algorithm for graph clustering using minimum cut tree. In: ICDM Workshops 2006. 6th IEEE International Conference on Data Mining Workshops, 2006, pp. 667\u2013671 (2006)"},{"issue":"4","key":"658_CR12","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"658_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0219009","volume":"19","author":"D Gusfield","year":"1990","unstructured":"Gusfield, D.: Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19(1), 143\u2013155 (1990)","journal-title":"SIAM J. Comput."},{"key":"658_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jpdc.2017.04.007","volume":"109","author":"J Cohen","year":"2017","unstructured":"Cohen, J., Rodrigues, L.A., Duarte Jr., E.P.: Parallel cut tree algorithms. J. Parallel Distrib. Comput. 109, 1\u201314 (2017)","journal-title":"J. Parallel Distrib. Comput."},{"key":"658_CR15","doi-asserted-by":"crossref","unstructured":"Adamic, L.A., Glance, N.: The political blogosphere and the 2004 u.s. election: Divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery, pp. 36\u201343. ACM (2005)","DOI":"10.1145\/1134271.1134277"},{"issue":"6684","key":"658_CR16","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"},{"key":"658_CR17","unstructured":"Storchi, G., Dell\u2019Olmo, P., Gentili, M.: Road network of the city of rome. In: 9th DIMACS Implementation Challenge\u2014Shortest Paths. Available at http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml (1999). Accessed 11 Dec 2019 (1999)"},{"key":"658_CR18","unstructured":"Batagelj, V., Mrvar, A.: Pajek datasets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data. Accessed 11 Dec 2019"},{"key":"658_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001). (Cambridge Books Online)","edition":"2"},{"key":"658_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47 (2002)","journal-title":"Rev. Mod. Phys."},{"issue":"1\u20133","key":"658_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01582226","volume":"67","author":"H Nagamochi","year":"1994","unstructured":"Nagamochi, H., Ono, T., Ibaraki, T.: Implementing an efficient minimum capacity cut algorithm. Math. Program. 67(1\u20133), 325\u2013341 (1994)","journal-title":"Math. Program."},{"key":"658_CR22","unstructured":"Chekuri, C.S., Goldberg, A.V., Karger, D.R., Levine, M.S., Stein, C.: Experimental study of minimum cut algorithms. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201997, pp. 324\u2013333. Society for Industrial and Applied Mathematics, Philadelphia (1997)"},{"key":"658_CR23","unstructured":"Goldberg, A.V., Tsioutsiouliklis, K.: Cut tree algorithms. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201999, pp. 376\u2013385. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"658_CR24","doi-asserted-by":"crossref","unstructured":"Anari, N., Vazirani, V. V.: Planar graph perfect matching is in NC. In: Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS\u20192018, pp. 650\u2013661 (2018)","DOI":"10.1109\/FOCS.2018.00068"},{"key":"658_CR25","doi-asserted-by":"crossref","unstructured":"Abboud, A., Krauthgamer, R., Trabelsi O.: New algorithms and lower bounds for all-pairs max-flow in undirected graphs In: Proceedings of the XXth ACM-Siam Symposium on Discrete Algorithms, SODA\u20192020 (2020)","DOI":"10.1137\/1.9781611975994.4"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00658-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00658-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00658-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:06:44Z","timestamp":1607818004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00658-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,14]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["658"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00658-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,12,14]]},"assertion":[{"value":"13 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}