{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089987,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319388502"},{"type":"electronic","value":"9783319388519"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_11","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:33:54Z","timestamp":1464708834000},"page":"150-166","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Subgraphs for 2-Connectivity in Directed Graphs"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]},{"given":"Aikaterini","family":"Karanasiou","sequence":"additional","affiliation":[]},{"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[]},{"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"key":"11_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK 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":"11_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 J. Comput. 28(6), 2117\u20132132 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"11_CR3","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"AL 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 J. Comput. 38(4), 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"11_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$$ k -connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"11_CR5","first-page":"91","volume-title":"Combinatorial Algorithms","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J.: Edge-disjoint branchings. In: Rustin, B. (ed.) Combinatorial Algorithms, pp. 91\u201396. Academic Press, New York (1972)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Laekhanukit, B.: An $$o(\\log ^2{k})$$ o ( log 2 k ) -approximation algorithm for the $$k$$ k -vertex connected spanning subgraph problem. In: Proceedings of the 40th ACM Symposium on Theory of Computing, STOC 2008, pp. 153\u2013158, New York, NY, USA, ACM (2008)","DOI":"10.1145\/1374376.1374401"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"issue":"2","key":"11_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR 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":"11_CR10","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. 6942, pp. 13\u201324. Springer, Heidelberg (2011)"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Italiano, G.F., Laura, L., Parotsidis, N.: 2-Edge connectivity in directed graphs. SODA 2015, pp. 1988\u20132005 (2015)","DOI":"10.1137\/1.9781611973730.132"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/978-3-662-47672-7_49","volume-title":"Automata, Languages, and Programming","author":"L Georgiadis","year":"2015","unstructured":"Georgiadis, L., Italiano, G.F., Laura, L., Parotsidis, N.: 2-Vertex connectivity in directed graphs. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 605\u2013616. Springer, Heidelberg (2015)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1007\/978-3-662-48350-3_49","volume-title":"Algorithms - ESA 2015","author":"L Georgiadis","year":"2015","unstructured":"Georgiadis, L., Italiano, G.F., Papadopoulos, C., Parotsidis, N.: Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015. LNCS, vol. 9294, pp. 582\u2013594. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_49"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Italiano, G.F., Parotsidis, N.: A new framework for strong connectivity and 2-connectivity in directed graphs. CoRR, November 2015. arXiv:1511.02913","DOI":"10.1137\/1.9781611973730.132"},{"issue":"1","key":"11_CR15","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2764913","volume":"12","author":"L Georgiadis","year":"2015","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree certification and divergent spanning trees. ACM Trans. Algorithms 12(1), 11:1\u201311:42 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/978-3-662-47672-7_58","volume-title":"Automata, Languages, and Programming","author":"M Henzinger","year":"2015","unstructured":"Henzinger, M., Krinninger, S., Loitzenbauer, V.: Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 713\u2013724. Springer, Heidelberg (2015)"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2011.11.011","volume":"447","author":"GF Italiano","year":"2012","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theor. Comput. Sci. 447, 74\u201384 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1051\/ita\/2015001","volume":"49","author":"R Jaberi","year":"2015","unstructured":"Jaberi, R.: Computing the $$2$$ 2 -blocks of directed graphs. RAIRO-Theor. Inf. Appl. 49(2), 93\u2013119 (2015)","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Jaberi, R.: On computing the 2-vertex-connected components of directed graphs. Discrete Applied Mathematics, (2015, to appear)","DOI":"10.1016\/j.dam.2015.10.001"},{"issue":"4","key":"11_CR20","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/S0097539793256685","volume":"24","author":"S Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: Approximating the minimum equivalent digraph. SIAM J. Comput. 24(4), 859\u2013872 (1995). Announced at SODA 1994, 177\u2013186","journal-title":"SIAM J. Comput."},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(95)00105-Z","volume":"69","author":"S Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: On strongly connected digraphs with bounded cycle length. Discrete Appl. Math. 69(3), 281\u2013289 (1996)","journal-title":"Discrete Appl. Math."},{"key":"11_CR22","volume-title":"Approximation Algorithms and Metaheuristics","author":"G Kortsarz","year":"2007","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Gonzalez, T.F. (ed.) Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC, Boca Raton (2007)"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/978-3-642-31594-7_51","volume-title":"Automata, Languages, and Programming","author":"B Laekhanukit","year":"2012","unstructured":"Laekhanukit, B., Oveis Gharan, S., Singh, M.: A rounding by sampling approach to the minimum size k-arc connected subgraph problem. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 606\u2013616. Springer, Heidelberg (2012)"},{"key":"11_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity, 1st edn. Cambridge University Press, New York (2008)","edition":"1"},{"issue":"2","key":"11_CR25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"11_CR26","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00268499","volume":"6","author":"RE Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Informatica 6(2), 171\u2013185 (1976)","journal-title":"Acta Informatica"},{"key":"11_CR27","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: SODA, pp. 417\u2013426 (2001)"},{"issue":"2","key":"11_CR28","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(02)00476-3","volume":"86","author":"L Zhao","year":"2003","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: A linear time 5\/3-approximation for the minimum strongly-connected spanning subgraph problem. Inf. Process. Lett. 86(2), 63\u201370 (2003)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T21:54:52Z","timestamp":1656626092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}