{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:42Z","timestamp":1759637862057},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_49","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"582-594","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs"],"prefix":"10.1007","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"issue":"6","key":"49_CR1","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":"49_CR2","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":"49_CR3","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":"49_CR4","unstructured":"Edmonds, J.: Edge-disjoint branchings. Combinat. Algorithms, 91\u201396 (1972)"},{"issue":"4","key":"49_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/net.20289","volume":"53","author":"H.N. Gabow","year":"2009","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, E., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by lp-rounding. Networks\u00a053(4), 345\u2013357 (2009)","journal-title":"Networks"},{"issue":"2","key":"49_CR6","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":"49_CR7","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":"49_CR8","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Italiano, G.F., Laura, L., Parotsidis, N.: 2-edge connectivity in directed graphs. In: SODA 2015, pp. 1988\u20132005 (2015)","DOI":"10.1137\/1.9781611973730.132"},{"key":"49_CR9","unstructured":"Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: SODA 2005, pp. 433\u2013442 (2005)"},{"key":"49_CR10","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Loitzenbauer, V.: Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: ICALP 2015, pp. 713\u2013724 (2015)","DOI":"10.1007\/978-3-662-47672-7_58"},{"key":"49_CR11","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. Theor. Comput. Sci.\u00a0447, 74\u201384 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"49_CR12","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-blocks of directed graphs. RAIRO-Theor. Inf. Appl.\u00a049(2), 93\u2013119 (2015)","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. Approximation Algorithms and Metaheuristics (2007)","DOI":"10.1201\/9781420010749.ch58"},{"key":"49_CR14","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.\u00a07391, pp. 606\u2013616. Springer, Heidelberg (2012)"},{"key":"49_CR15","doi-asserted-by":"crossref","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity, 1st edn. Cambridge University Press (2008)","DOI":"10.1017\/CBO9780511721649"},{"issue":"2","key":"49_CR16","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"},{"key":"49_CR17","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: SODA 2001, pp. 417\u2013426 (2001)"},{"issue":"2","key":"49_CR18","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. Information Processing Letters\u00a086(2), 63\u201370 (2003)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T15:57:06Z","timestamp":1559231826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}