{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:28Z","timestamp":1746331408493,"version":"3.40.4"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079585"},{"type":"electronic","value":"9783319079592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_15","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:44:25Z","timestamp":1402418665000},"page":"174-186","source":"Crossref","is-referenced-by-count":3,"title":["Loop Nesting Forests, Dominators, and Applications"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[]},{"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"A.V. Aho","year":"1986","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading (1986)"},{"key":"15_CR2","unstructured":"Aho, A.V., Ullman, J.D.: Principles of Compilers Design. Addison-Wesley (1977)"},{"issue":"6","key":"15_CR3","doi-asserted-by":"publisher","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 Journal on Computing\u00a028(6), 2117\u20132132 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR4","unstructured":"Amyeen, M.E., Fuchs, W.K., Pomeranz, I., Boppana, V.: Fault equivalence identification using redundancy information and static and dynamic extraction. In: Proceedings of the 19th IEEE VLSI Test Symposium (March 2001)"},{"issue":"4","key":"15_CR5","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"A.L. 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 Journal on Computing\u00a038(4), 1533\u20131573 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"#cr-split#-15_CR6.1","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: A new, simpler linear-time dominators algorithm. ACM Transactions on Programming Languages and Systems\u00a020(6), 1265-1296 (1998)","DOI":"10.1145\/295656.295663"},{"key":"#cr-split#-15_CR6.2","doi-asserted-by":"crossref","unstructured":"Corrigendum in 27(3), 383-387 (2005)","DOI":"10.1145\/1065887.1065888"},{"key":"15_CR7","unstructured":"CAD Benchmarking Lab. ISCAS 1989 benchmark information, http:\/\/www.cbl.ncsu.edu\/www\/CBL_Docs\/iscas89.html"},{"key":"15_CR8","first-page":"110","volume":"4","author":"K.D. Cooper","year":"2001","unstructured":"Cooper, K.D., Harvey, T.J., Kennedy, K.: A simple, fast dominance algorithm. Software Practice & Experience\u00a04, 110 (2001)","journal-title":"Software Practice & Experience"},{"issue":"4","key":"15_CR9","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1145\/115372.115320","volume":"13","author":"R. Cytron","year":"1991","unstructured":"Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.: Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems\u00a013(4), 451\u2013490 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"15_CR10","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: 9th DIMACS Implementation Challenge: Shortest Paths (2007), http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-30850-5_18","volume-title":"Experimental Algorithms","author":"D. Firmani","year":"2012","unstructured":"Firmani, D., Italiano, G.F., Laura, L., Orlandi, A., Santaroni, F.: Computing strong articulation points and strong bridges in large scale graphs. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 195\u2013207. Springer, Heidelberg (2012)"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.10.003","volume":"23","author":"W. Fraczak","year":"2013","unstructured":"Fraczak, W., Georgiadis, L., Miller, A., Tarjan, R.E.: Finding dominators via disjoint set union. Journal of Discrete Algorithms\u00a023, 2\u201320 (2013)","journal-title":"Journal of Discrete Algorithms"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: Applications of a poset representation to edge connectivity and graph rigidity. In: Proc. 32th IEEE Symp. on Foundations of Computer Science, pp. 812\u2013821 (1991)","DOI":"10.1109\/SFCS.1991.185453"},{"key":"15_CR14","unstructured":"Gabow, H.N.: The minimal-set poset for edge connectivity (2013) (unpublished manuscript)"},{"key":"15_CR15","unstructured":"Gabow, H.N.: A poset approach to dominator computation (2013) (unpublished manuscript 2010, revised unpublished manuscript)"},{"issue":"2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences\u00a030(2), 209\u2013221 (1985)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/978-3-540-92182-0_62","volume-title":"Algorithms and Computation","author":"L. Georgiadis","year":"2008","unstructured":"Georgiadis, L.: Computing frequency dominators and related problems. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 704\u2013715. Springer, Heidelberg (2008)"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-642-14165-2_62","volume-title":"Automata, Languages and Programming","author":"L. Georgiadis","year":"2010","unstructured":"Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 738\u2013749. Springer, Heidelberg (2010)"},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-23719-5_2","volume-title":"Algorithms \u2013 ESA 2011","author":"L. Georgiadis","year":"2011","unstructured":"Georgiadis, L.: Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 13\u201324. Springer, Heidelberg (2011)"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-642-38527-8_26","volume-title":"Experimental Algorithms","author":"L. Georgiadis","year":"2013","unstructured":"Georgiadis, L., Laura, L., Parotsidis, N., Tarjan, R.E.: Dominator certification and independent spanning trees: An experimental study. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 284\u2013295. Springer, Heidelberg (2013)"},{"key":"15_CR21","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 862\u2013871 (2004)"},{"key":"15_CR22","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. 433\u2013442 (2005)"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree certification and independent spanning trees. CoRR, abs\/1210.8303 (2012)","DOI":"10.1007\/978-3-642-31594-7_32"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominators, directed bipolar orders, and independent spanning trees. In: Proc. 39th Int\u2019l. Coll. on Automata, Languages, and Programming, pp. 375\u2013386 (2012)","DOI":"10.1007\/978-3-642-31594-7_32"},{"issue":"1","key":"15_CR25","doi-asserted-by":"publisher","first-page":"69","DOI":"10.7155\/jgaa.00119","volume":"10","author":"L. Georgiadis","year":"2006","unstructured":"Georgiadis, L., Tarjan, R.E., Werneck, R.F.: Finding dominators in practice. Journal of Graph Algorithms and Applications (JGAA)\u00a010(1), 69\u201394 (2006)","journal-title":"Journal of Graph Algorithms and Applications (JGAA)"},{"issue":"4","key":"15_CR26","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/262004.262005","volume":"19","author":"P. Havlak","year":"1997","unstructured":"Havlak, P.: Nesting of reducible and irreducible loops. ACM Transactions on Programming Languages and Systems\u00a019(4), 557\u2013567 (1997)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2011.11.011","volume":"447","author":"G.F. Italiano","year":"2012","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science\u00a0447, 74\u201384 (2012)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"15_CR28","doi-asserted-by":"publisher","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 Transactions on Programming Languages and Systems\u00a01(1), 121\u2013141 (1979)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"15_CR29","unstructured":"Leskovec, J.: Stanford large network dataset collection (2009), http:\/\/snap.stanford.edu"},{"key":"15_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/11785477_5","volume-title":"ECOOP 2006 \u2013 Object-Oriented Programming","author":"N. Mitchell","year":"2006","unstructured":"Mitchell, N.: The runtime structure of object ownership. In: Thomas, D. (ed.) ECOOP 2006. LNCS, vol.\u00a04067, pp. 74\u201398. Springer, Heidelberg (2006)"},{"issue":"5","key":"15_CR31","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/570886.570887","volume":"24","author":"G. Ramalingam","year":"2002","unstructured":"Ramalingam, G.: On loops, dominators, and dominance frontiers. ACM Transactions on Programming Languages and Systems\u00a024(5), 455\u2013490 (2002)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"15_CR32","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees, dominators, and depth-first search. Technical report, Stanford University, Stanford, CA, USA (1974)"},{"issue":"2","key":"15_CR33","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. Journal of the ACM\u00a022(2), 215\u2013225 (1975)","journal-title":"Journal of the ACM"},{"issue":"2","key":"15_CR34","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00268499","volume":"6","author":"R.E. Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Informatica\u00a06(2), 171\u2013185 (1976)","journal-title":"Acta Informatica"},{"issue":"4","key":"15_CR35","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. Journal of the ACM\u00a026(4), 690\u2013715 (1979)","journal-title":"Journal of the ACM"},{"issue":"3","key":"15_CR36","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1145\/322261.322273","volume":"28","author":"R.E. Tarjan","year":"1981","unstructured":"Tarjan, R.E.: Fast algorithms for solving path problems. Journal of the ACM\u00a028(3), 594\u2013614 (1981)","journal-title":"Journal of the ACM"},{"issue":"2","key":"15_CR37","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. Journal of the ACM\u00a031(2), 245\u2013281 (1984)","journal-title":"Journal of the ACM"},{"key":"15_CR38","unstructured":"The WebGraph Framework Home Page, http:\/\/webgraph.dsi.unimi.it\/"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:04:15Z","timestamp":1746263055000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}