{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:33:50Z","timestamp":1725701630079},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_43","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"491-502","source":"Crossref","is-referenced-by-count":6,"title":["An Experimental Study of Dynamic Dominators"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[]},{"given":"Federico","family":"Santaroni","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"43_CR1","unstructured":"Allen, F.E., Cocke, J.: Graph theoretic constructs for program control flow analysis. Technical Report IBM RC 3923, IBM T.J. Watson Research (1972)"},{"issue":"6","key":"43_CR2","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":"43_CR3","unstructured":"Alstrup, S., Lauridsen, P.W.: A simple dynamic algorithm for maintaining a dominator tree. Technical Report 96-3, Department of Computer Science, University of Copenhagen (1996)"},{"issue":"4","key":"43_CR4","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"},{"issue":"3","key":"43_CR5","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1145\/1065887.1065888","volume":"27","author":"A.L. Buchsbaum","year":"2005","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: A new, simpler linear-time dominators algorithm. ACM Trans. on Programming Languages and Systems\u00a027(3), 383\u2013387 (2005)","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"43_CR6","doi-asserted-by":"crossref","unstructured":"Carroll, M.D., Ryder, B.G.: Incremental data flow analysis via dominator and attribute update. In: Proc. 15th ACM POPL, pp. 274\u2013284 (1988)","DOI":"10.1145\/73560.73584"},{"key":"43_CR7","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(97)00288-0","volume":"203","author":"S. Cicerone","year":"1998","unstructured":"Cicerone, S., Frigioni, D., Nanni, U., Pugliese, F.: A uniform approach to semi-dynamic problems on digraphs. Theor. Comput. Sci.\u00a0203, 69\u201390 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"43_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"},{"key":"43_CR9","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS Implementation Challenge - Shortest Paths (2006)"},{"key":"43_CR10","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":"43_CR11","unstructured":"Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proc. 1st ACM-SIAM SODA, pp. 434\u2013443 (1990)"},{"key":"43_CR12","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, Part I. LNCS, vol.\u00a06198, pp. 738\u2013749. Springer, Heidelberg (2010)"},{"key":"43_CR13","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":"43_CR14","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proc. 15th ACM-SIAM SODA, pp. 862\u2013871 (2004)"},{"key":"43_CR15","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proc.\u00a016th ACM-SIAM SODA, pp. 433\u2013442 (2005)"},{"key":"43_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-31594-7_32","volume-title":"Automata, Languages, and Programming","author":"L. Georgiadis","year":"2012","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominators, Directed Bipolar Orders, and Independent Spanning Trees. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 375\u2013386. Springer, Heidelberg (2012)"},{"issue":"1","key":"43_CR17","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)"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science (to appear, 2012)","DOI":"10.1016\/j.tcs.2011.11.011"},{"issue":"1","key":"43_CR19","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 Trans. on Programming Languages and Systems\u00a01(1), 121\u2013141 (1979)","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"43_CR20","doi-asserted-by":"crossref","unstructured":"Maxwell, E.K., Back, G., Ramakrishnan, N.: Diagnosing memory leaks using graph mining on heap dumps. In: Proc. 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD 2010, pp. 115\u2013124 (2010)","DOI":"10.1145\/1835804.1835822"},{"key":"43_CR21","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: Hu, Q. (ed.) ECOOP 2006. LNCS, vol.\u00a04067, pp. 74\u201398. Springer, Heidelberg (2006)"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Patakakis, K., Georgiadis, L., Tatsis, V.A.: Dynamic dominators in practice. In: Proc. 16th Panhellenic Conference on Informatics, pp. 100\u2013104 (2011)","DOI":"10.1109\/PCI.2011.28"},{"issue":"8","key":"43_CR23","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1145\/361532.361566","volume":"15","author":"P.W. Purdom Jr.","year":"1972","unstructured":"Purdom Jr., P.W., Moore, E.F.: Algorithm 430: Immediate predominators in a directed graph. Communications of the ACM\u00a015(8), 777\u2013778 (1972)","journal-title":"Communications of the ACM"},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Ramalingam, G., Reps, T.: An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In: Proc. 21st ACM POPL, pp. 287\u2013296 (1994)","DOI":"10.1145\/174675.177905"},{"key":"43_CR25","unstructured":"Sreedhar, V.C.: Efficient program analysis using DJ graphs. PhD thesis, School of Computer Science, McGill University (September 1995)"},{"key":"43_CR26","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1145\/244795.244799","volume":"19","author":"V.C. Sreedhar","year":"1997","unstructured":"Sreedhar, V.C., Gao, G.R., Lee, Y.: Incremental computation of dominator trees. ACM Trans. Program. Lang. Syst.\u00a019, 239\u2013252 (1997)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"43_CR27","unstructured":"Stanford network analysis platform (SNAP), \n                  \n                    http:\/\/snap.stanford.edu\/"},{"issue":"1","key":"43_CR28","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1137\/0203006","volume":"3","author":"R.E. Tarjan","year":"1974","unstructured":"Tarjan, R.E.: Finding dominators in directed graphs. SIAM Journal on Computing\u00a03(1), 62\u201389 (1974)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"43_CR29","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:58Z","timestamp":1620129298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}