{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:28Z","timestamp":1760202688205},"reference-count":31,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1051\/ita\/2015001","type":"journal-article","created":{"date-parts":[[2015,4,16]],"date-time":"2015-04-16T02:34:02Z","timestamp":1429151642000},"page":"93-119","source":"Crossref","is-referenced-by-count":8,"title":["Computing the 2-blocks of directed graphs"],"prefix":"10.1051","volume":"49","author":[{"given":"Raed","family":"Jaberi","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"R1","unstructured":"Alstrup S., Harel D., Lauridsen P.W. and Thorup M., Dominators in linear time.SIAM J. Comput.28(1999) 2117\u20132132."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"R. Balakrishnan and K. Ranganathan, A Textbook of graph theory, 2nd edn. Springer (2012) 66.","DOI":"10.1007\/978-1-4614-4529-6"},{"key":"R3","unstructured":"Buchsbaum A.L., Georgiadis L., Kaplan H., Rogers A., Tarjan R.E. and Westbrook J.R., Linear-time algorithms for dominators and other path-evaluation problems.SIAM J. Comput.38(2008) 1533\u20131573."},{"key":"R4","unstructured":"J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark, k-Blocks, a connectivity invariant for graphs (2013). Preprint ArXiv:1305.4557."},{"key":"R5","unstructured":"Cheriyan J. and Thurimella R., Approximating minimum-size k-connected spanning subgraphs via matching.SIAM J. Comput.30(2000) 528\u2013560."},{"key":"R6","unstructured":"Erusalimskii Y.M. and Svetlov G.G., Bijoin points, bibridges, and biblocks of directed graphs.Cybernet. Systems Anal.16(1980) 41\u201344."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Firmani D., Italiano G.F., Laura L., Orlandi A. and Santaroni F., Computing strong articulation points and strong bridges in large scale graphs, SEA.Lect. Notes Comput. Sci.7276(2012) 195\u2013207.","DOI":"10.1007\/978-3-642-30850-5_18"},{"key":"R8","unstructured":"Fortune S., Hopcroft J.E. and Wyllie J., The Directed Subgraph Homeomorphism Problem.Theoret. Comput. Sci.10(1980) 111\u2013121."},{"key":"R9","unstructured":"Frederickson G.N., J\u00e1J\u00e1 J., Approximation Algorithms for Several Graph Augmentation Problems.SIAM J. Comput.10(1981) 270\u2013283."},{"key":"R10","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco (1979)."},{"key":"R11","unstructured":"Gavril F., Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph.SIAM J. Comput.1(1972) 180\u2013187."},{"key":"R12","unstructured":"L. Georgiadis, Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In vol. 6189 ofProc. of 37th ICALP, Part I.Lect. Notes Comput. Sci.(2010) 738\u2013749."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, InProc. of 19th European Symposium on Algorithms(2011) 13\u201324.","DOI":"10.1007\/978-3-642-23719-5_2"},{"key":"R14","unstructured":"L. Georgiadis and R.E. Tarjan, Dominator tree verification and vertex- disjoint paths, InProc. of the 16th ACM-SIAM Symposium on Discrete Algorithms(2005) 433\u2013442."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Georgiadis L. and Tarjan R.E., Dominators, Directed Bipolar Orders, and Independent Spanning Trees.ICALP(2012) 375\u2013386.","DOI":"10.1007\/978-3-642-31594-7_32"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Edge Connectivity in Directed Graphs, CoRR abs\/1407.3041 (2014).","DOI":"10.1137\/1.9781611973730.132"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Vertex Connectivity in Directed Graphs, CoRR abs\/1409.6277 (2014).","DOI":"10.1137\/1.9781611973730.132"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, G.F. Italiano, L. Laura and N. Parotsidis, 2-Edge Connectivity in Directed Graphs, SODA (2015) 1988\u20132005.","DOI":"10.1137\/1.9781611973730.132"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Goldberg A.V. and Tarjan R.E., Efficient maximum flow algorithms.Commun. ACM57(2014) 82\u201389.","DOI":"10.1145\/2628036"},{"key":"R20","unstructured":"Italiano G.F., Laura L. and Santaroni F., Finding strong bridges and strong articulation points in linear time.Theoret. Comput. Sci.447(2012) 74\u201384."},{"key":"R21","unstructured":"R. Jaberi, On Computing the 2-vertex-connected components of directed graphs, CoRR abs\/1401.6000 (2014)."},{"key":"R22","unstructured":"Khuller S., Raghavachari B. and Young N.E., Approximating the Minimum Equivalent Diagraph.SODA(1994) 177\u2013186."},{"key":"R23","unstructured":"Lengauer T. and Tarjan R.E., A fast algorithm for finding dominators in a flowgraph.ACM Trans. Program. Lang. Syst.1(1979) 121\u2013141."},{"key":"R24","unstructured":"Li Chung-Lun, Thomas McCormick S. and Simchi-Levi D., The complexity of finding two disjoint paths with min-max objective function.Discrete. Appl. Math.26(1990) 105\u2013115."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Lowry E.S. and Medlock C.W., Object code optimization.Commun. ACM12(1969) 13\u201322.","DOI":"10.1145\/362835.362838"},{"key":"R26","unstructured":"J.B. Orlin, Max Flows in O(nm) time, or better. InProc. of the Annual ACM Symposium on Theory of Computing. ACM Press, New York (2011) 765\u2013774."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"D.J. Rose and R.E. Tarjan, Algorithmic Aspects of Vertex Elimination.Proc. of 7e Annual ACM Symposium on Theory of Computing. ACM Press, New York (1975) 245\u2013254.","DOI":"10.1145\/800116.803775"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Tarjan R.E., Depth-first search and linear graph algorithms.SIAM J. Comput.1(1972). 146\u2013160","DOI":"10.1137\/0201010"},{"key":"R29","unstructured":"Tarjan R.E., Edge-disjoint spanning trees and depth-first search.Acta Inf.6(1976) 171\u2013185."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"S. Vempala and A. Vetta, Factor 4\/3 approximations for minimum 2-connected subgraphs.Proc. of APPROX(2000) 262\u2013273.","DOI":"10.1007\/3-540-44436-X_26"},{"key":"R31","unstructured":"Zhao L., Nagamochi H. and Ibaraki T., A linear time 5\/3-approximation for the minimum strongly-connected spanning subgraph problem.Inf. Process. Lett.86(2003) 63\u201370."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015001\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T11:03:53Z","timestamp":1566558233000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":31,"journal-issue":{"issue":"2"},"alternative-id":["ita140038"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2015001","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}