{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:21Z","timestamp":1759638681010},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_62","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"738-749","source":"Crossref","is-referenced-by-count":17,"title":["Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"62_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)"},{"issue":"6","key":"62_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":"62_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-3886-0","volume-title":"Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics)","author":"J. Bang-Jensen","year":"2002","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics), 1st edn., 3rd printing edn. Springer, Heidelberg (2002)","edition":"1"},{"issue":"1","key":"62_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci.\u00a065(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"62_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"},{"issue":"6","key":"62_CR6","doi-asserted-by":"crossref","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 appeared 27(3), 383-387 (2005)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"2","key":"62_CR7","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/07068669X","volume":"39","author":"T.M. Chan","year":"2009","unstructured":"Chan, T.M., Patra\u015fcu, M.: Transdichotomous results in computational geometry, i: Point location in sublogarithmic time. SIAM Journal on Computing\u00a039(2), 703\u2013729 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"62_CR8","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM Journal on Computing\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"62_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)","DOI":"10.1007\/BF01302965"},{"issue":"3","key":"62_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput.\u00a09(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"62_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stei, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)","edition":"2"},{"issue":"5","key":"62_CR12","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1145\/1183907.1183912","volume":"53","author":"H.N. Gabow","year":"2006","unstructured":"Gabow, H.N.: Using expander graphs to find vertex connectivity. Journal of the ACM\u00a053(5), 800\u2013844 (2006)","journal-title":"Journal of the ACM"},{"issue":"2","key":"62_CR13","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":"62_CR14","unstructured":"Georgiadis, L.: Linear-Time Algorithms for Dominators and Related Problems. PhD thesis, Princeton University (2005)"},{"key":"62_CR15","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 862\u2013871 (2004)"},{"key":"62_CR16","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)"},{"issue":"1","key":"62_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.: 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":"62_CR18","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1999.1055","volume":"34","author":"M.R. Henzinger","year":"2000","unstructured":"Henzinger, M.R., Rao, S., Gabow, H.N.: Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms\u00a034, 222\u2013250 (2000)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"62_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM Journal on Computing\u00a02(3), 135\u2013158 (1973)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"62_CR20","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":"62_CR21","doi-asserted-by":"crossref","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07, 583\u2013596","DOI":"10.1007\/BF01758778"},{"issue":"7","key":"62_CR22","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Communications of the ACM\u00a029(7), 669\u2013679 (1986)","journal-title":"Communications of the ACM"},{"issue":"2","key":"62_CR23","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":"2","key":"62_CR24","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"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_62.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:23Z","timestamp":1606186103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}