{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:47Z","timestamp":1759063427365},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_2","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"13-24","source":"Crossref","is-referenced-by-count":7,"title":["Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"Network flows: theory, algorithms, and applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows: theory, algorithms, and applications. Prentice-Hall, Inc., Upper Saddle River (1993)"},{"issue":"6","key":"2_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"},{"issue":"4","key":"2_CR3","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":"2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J. Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput.\u00a030(2), 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: 25th International Parallel and Distributed Processing Symposium, IPDPS 2011 (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"2_CR6","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Springer, New York (2000)","edition":"2"},{"key":"2_CR7","unstructured":"Edmonds, J.: Edge-disjoint branchings. Combinatorial Algorithms, 91\u201396 (1972)"},{"key":"2_CR8","unstructured":"Gabow, H.N., Gallagher, S.: Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 550\u2013559 (2008)"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM\u00a038, 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"2_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"2_CR11","unstructured":"Garg, N., Santosh, V.S., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 103\u2013111 (1993)"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In: Proc. 37th Int\u2019l. Coll. on Automata, Languages, and Programming, pp. 738\u2013749 (2010)","DOI":"10.1007\/978-3-642-14165-2_62"},{"key":"2_CR13","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 862\u2013871 (2004)"},{"key":"2_CR14","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":"2_CR15","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":"2_CR16","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. Journal of the ACM\u00a035, 921\u2013940 (1988)","journal-title":"Journal of the ACM"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a02, 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-642-17458-2_14","volume-title":"Combinatorial Optimization and Applications","author":"G. Italiano","year":"2010","unstructured":"Italiano, G., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part I. LNCS, vol.\u00a06508, pp. 157\u2013169. Springer, Heidelberg (2010)"},{"issue":"1","key":"2_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 Transactions on Programming Languages and Systems\u00a01(1), 121\u2013141 (1979)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"2","key":"2_CR20","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/0095-8956(85)90076-0","volume":"38","author":"W. Mader","year":"1985","unstructured":"Mader, W.: Minimal n-fach zusammenh\u00e4ngende digraphen. Journal of Combinatorial Theory, Series B\u00a038(2), 102\u2013117 (1985)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: An almost O(logk)-approximation for k-connected subgraphs. In: Proc. 20th ACM-SIAM Symp. on Discrete Algorithms, SODA 2009, pp. 912\u2013921 (2009)","DOI":"10.1137\/1.9781611973068.99"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences\u00a026, 362\u2013391 (1983)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR23","unstructured":"Stanford network analysis platform (snap), http:\/\/snap.stanford.edu\/"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:08:09Z","timestamp":1560528489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}