{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:46:33Z","timestamp":1767926793008,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642385261","type":"print"},{"value":"9783642385278","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38527-8_26","type":"book-chapter","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T13:23:02Z","timestamp":1368019382000},"page":"284-295","source":"Crossref","is-referenced-by-count":5,"title":["Dominator Certification and Independent Spanning Trees: An Experimental Study"],"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":"26_CR1","unstructured":"Allen, F.E., Cocke, J.: Graph theoretic constructs for program control flow analysis. Tech. Rep. IBM Res. Rep. RC 3923, IBM T.J. Watson Research Center (1972)"},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/j.jtbi.2004.05.009","volume":"230","author":"S. Allesina","year":"2004","unstructured":"Allesina, S., Bodini, A.: Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions. Journal of Theoretical Biology\u00a0230(3), 351\u2013358 (2004)","journal-title":"Journal of Theoretical Biology"},{"issue":"6","key":"26_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":"26_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)"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-45749-6_17","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 152\u2013164. Springer, Heidelberg (2002)"},{"issue":"4","key":"26_CR6","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":"6","key":"26_CR7","doi-asserted-by":"publisher","first-page":"1265","DOI":"10.1145\/295656.295663","volume":"20","author":"A.L. Buchsbaum","year":"1998","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\u20131296 (1998); Corrigendum in 27(3), 383\u2013387 (2005)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"26_CR8","unstructured":"CAD Benchmarking Lab: ISCAS\u201989 benchmark information, \n                    \n                      http:\/\/www.cbl.ncsu.edu\/www\/CBL_Docs\/iscas89.html"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Reif, J.H.: Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity. Combinatorica, 435\u2013451 (1994), also in SODA 1992","DOI":"10.1007\/BF01302965"},{"key":"26_CR10","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":"26_CR11","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":"26_CR12","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS Implementation Challenge: Shortest Paths (2007), \n                    \n                      http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: Proc. 19th ACM Symp. on Theory of Computing, pp. 365\u2013372 (1987)","DOI":"10.1145\/28395.28434"},{"key":"26_CR14","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":"26_CR15","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":"26_CR16","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":"26_CR17","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 862\u2013871 (2004)"},{"key":"26_CR18","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":"26_CR19","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree certification and independent spanning trees. CoRR abs\/1210.8303 (2012) (submitted for journal publication)"},{"key":"26_CR20","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":"26_CR21","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":"26_CR22","unstructured":"Gomez-Rodriguez, M., Sch\u00f6lkopf, B.: Influence maximization in continuous time diffusion networks. In: 29th International Conference on Machine Learning, ICML (2012)"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01202468","volume":"10","author":"A. Huck","year":"1994","unstructured":"Huck, A.: Independent trees in graphs. Graphs and Combinatorics\u00a010, 29\u201345 (1994)","journal-title":"Graphs and Combinatorics"},{"key":"26_CR24","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":"26_CR25","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":"26_CR26","unstructured":"Leskovec, J.: Stanford large network dataset collection (2009), \n                    \n                      http:\/\/snap.stanford.edu"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Maxwell, E.K., Back, G., Ramakrishnan, N.: Diagnosing memory leaks using graph mining on heap dumps. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2010, pp. 115\u2013124 (2010)","DOI":"10.1145\/1835804.1835822"},{"issue":"2","key":"26_CR28","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"R.M. McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Computer Science Review\u00a05(2), 119\u2013161 (2011)","journal-title":"Computer Science Review"},{"key":"26_CR29","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)"},{"key":"26_CR30","unstructured":"Plehn, J.: \u00dcber die Existenz und das Finden von Subgraphen. Ph.D. thesis, University of Bonn, Germany (May 1991)"},{"issue":"8","key":"26_CR31","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":"26_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/11603023_6","volume-title":"Practical Aspects of Declarative Languages","author":"L. Quesada","year":"2006","unstructured":"Quesada, L., Van Roy, P., Deville, Y., Collet, R.: Using dominators for solving constrained path problems. In: Van Hentenryck, P. (ed.) PADL 2006. LNCS, vol.\u00a03819, pp. 73\u201387. Springer, Heidelberg (2006)"},{"issue":"2","key":"26_CR33","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM Journal on Computing\u00a01(2), 146\u2013159 (1972)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR34","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":"26_CR35","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"},{"key":"26_CR36","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1002\/jgt.3190110309","volume":"11","author":"R.W. Whitty","year":"1987","unstructured":"Whitty, R.W.: Vertex-disjoint paths and edge-disjoint branchings in directed graphs. Journal of Graph Theory\u00a011, 349\u2013358 (1987)","journal-title":"Journal of Graph Theory"},{"key":"26_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-35308-6_6","volume-title":"Certified Programs and Proofs","author":"J. Zhao","year":"2012","unstructured":"Zhao, J., Zdancewic, S.: Mechanized verification of computing dominators for formalizing compilers. In: Hawblitzel, C., Miller, D. (eds.) CPP 2012. LNCS, vol.\u00a07679, pp. 27\u201342. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38527-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T23:42:18Z","timestamp":1557704538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38527-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385261","9783642385278"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38527-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}