{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:16:53Z","timestamp":1772468213430,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00453-015-9991-z","type":"journal-article","created":{"date-parts":[[2015,4,2]],"date-time":"2015-04-02T19:10:00Z","timestamp":1428001800000},"page":"1123-1147","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Strong Articulation Points and Strong Bridges in Large Scale Graphs"],"prefix":"10.1007","volume":"74","author":[{"given":"Donatella","family":"Firmani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loukas","family":"Georgiadis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Federico","family":"Santaroni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,1]]},"reference":[{"issue":"1","key":"9991_CR1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1137\/0205011","volume":"5","author":"AV Aho","year":"1976","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. SIAM J. Comput. 5(1), 115\u201332 (1976)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9991_CR2","doi-asserted-by":"crossref","first-page":"2117","DOI":"10.1137\/S0097539797317263","volume":"28","author":"S Alstrup","year":"1999","unstructured":"Alstrup, S., Harel, D., Lauridsen, P.W., Thorup, M.: Dominators in linear time. SIAM J. Comput. 28(6), 2117\u20132132 (1999)","journal-title":"SIAM J. Comput."},{"key":"9991_CR3","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., Flener, P., Lorca, X.: The tree constraint. In: Proceedings of the 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2005), vol. 3524 of LNCS, pp. 64\u201378. Springer, 30 May\u2013June 1 (2005)","DOI":"10.1007\/11493853_7"},{"key":"9991_CR4","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004), Manhattan, USA, pp. 595\u2013601. ACM Press (2004)","DOI":"10.1145\/988672.988752"},{"issue":"4","key":"9991_CR5","doi-asserted-by":"crossref","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"AL Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Georgiadis, L., Kaplan, H., Rogers, A., Tarjan, R.E., Westbrook, J.R.: Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38(4), 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"key":"9991_CR6","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: A new, simpler linear-time dominators algorithm. ACM Trans. Program. Lang. Syst. 20(6), 1265\u20131296 (1998). Corrigendum in 27(3):383\u2013387 (2005)"},{"key":"9991_CR7","first-page":"110","volume":"4","author":"KD Cooper","year":"2001","unstructured":"Cooper, K.D., Harvey, T.J., Kennedy, K.: A simple, fast dominance algorithm. Softw. Pract. Exp. 4, 110 (2001)","journal-title":"Softw. Pract. Exp."},{"key":"9991_CR8","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, London (2009)","edition":"3"},{"key":"9991_CR9","doi-asserted-by":"crossref","unstructured":"Firmani, D., Italiano, G.F., Laura, L., Orlandi, A., Santaroni, F.: Computing strong articulation points and strong bridges in large scale graphs. In: Proceedings of the 11th International Symposium on Experimental Algorithms (SEA), pp. 195\u2013207 (2012)","DOI":"10.1007\/978-3-642-30850-5_18"},{"issue":"2","key":"9991_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"9991_CR11","doi-asserted-by":"crossref","unstructured":"Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In: ICALP 10: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, pp. 433\u2013442 (2010)","DOI":"10.1007\/978-3-642-14165-2_62"},{"key":"9991_CR12","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Laura, L., Parotsidis, N., Tarjan, R.E.: Dominator certification and independent spanning trees: an experimental study. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA), pp. 284\u2013295. Springer (2013)","DOI":"10.1007\/978-3-642-38527-8_26"},{"key":"9991_CR13","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Laura, L., Parotsidis, N., Tarjan, R.E.: Loop nesting forests, dominators, and applications. In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA), pp. 174\u2013186. Springer (2014)","DOI":"10.1007\/978-3-319-07959-2_15"},{"key":"9991_CR14","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 862\u2013871 (2004)"},{"key":"9991_CR15","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 433\u2013442 (2005)"},{"key":"9991_CR16","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominators, directed bipolar orders, and independent spanning trees. In: Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 375\u2013386. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_32"},{"issue":"1","key":"9991_CR17","doi-asserted-by":"crossref","first-page":"69","DOI":"10.7155\/jgaa.00119","volume":"10","author":"L Georgiadis","year":"2006","unstructured":"Georgiadis, L., Tarjan, R.E., Werneck, R.F.F.: Finding dominators in practice. J. Graph Algorithms Appl. 10(1), 69\u201394 (2006)","journal-title":"J. Graph Algorithms Appl."},{"key":"9991_CR18","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2011.11.011","volume":"447","author":"GF Italiano","year":"2012","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theor. Comput. Sci. 447, 74\u201384 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9991_CR19","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/357062.357071","volume":"1","author":"T Lengauer","year":"1979","unstructured":"Lengauer, T., Tarjan, R.E.: A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1(1), 121\u2013141 (1979)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9991_CR20","doi-asserted-by":"crossref","unstructured":"Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC\u201907, New York, NY, USA, pp. 29\u201342. ACM (2007)","DOI":"10.1145\/1298306.1298311"},{"key":"9991_CR21","unstructured":"SNAP: Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/"},{"issue":"2","key":"9991_CR22","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u201359 (1972)","journal-title":"SIAM J. Comput."},{"key":"9991_CR23","unstructured":"Tarjan, R.E.: Edge-Disjoint Spanning Trees, Dominators, and Depth-First Search. Technical report, Stanford University, Stanford, CA (1974)"},{"issue":"2","key":"9991_CR24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"9991_CR25","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00268499","volume":"6","author":"RE Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Inf. 6, 171\u2013185 (1976)","journal-title":"Acta Inf."},{"issue":"4","key":"9991_CR26","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM 26(4), 690\u2013715 (1979)","journal-title":"J. ACM"},{"key":"9991_CR27","unstructured":"The WebGraph Framework Home Page. http:\/\/webgraph.dsi.unimi.it\/"},{"issue":"6","key":"9991_CR28","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.ipl.2007.04.004","volume":"103","author":"L Volkmann","year":"2007","unstructured":"Volkmann, L.: Restricted arc-connectivity of digraphs. Inf. Process. Lett. 103(6), 234\u2013239 (2007)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9991-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9991-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9991-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9991-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9991"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9991-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,1]]}}}