{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T02:17:42Z","timestamp":1623809862476},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,10,10]],"date-time":"2016-10-10T00:00:00Z","timestamp":1476057600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University and Research"},{"DOI":"10.13039\/501100003407","name":"MIUR","doi-asserted-by":"crossref"},{"name":"Italian Ministry of Education"},{"name":"AMANDA"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,12,21]]},"abstract":"\n Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices\n v<\/jats:italic>\n and\n w<\/jats:italic>\n are 2-\n edge-connected<\/jats:italic>\n if there are two edge-disjoint paths from\n v<\/jats:italic>\n to\n w<\/jats:italic>\n and two edge-disjoint paths from\n w<\/jats:italic>\n to\n v<\/jats:italic>\n . This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this article is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, when two query vertices\n v<\/jats:italic>\n and\n w<\/jats:italic>\n are not 2-edge-connected, we can produce in constant time a \u201cwitness\u201d of this property by exhibiting an edge that is contained in all paths from\n v<\/jats:italic>\n to\n w<\/jats:italic>\n or in all paths from\n w<\/jats:italic>\n to\n v<\/jats:italic>\n . We are also able to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) edges and maintains the same 2-edge-connected blocks as the input graph, where\n n<\/jats:italic>\n is the number of vertices.\n <\/jats:p>","DOI":"10.1145\/2968448","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T18:01:35Z","timestamp":1476208895000},"page":"1-24","source":"Crossref","is-referenced-by-count":9,"title":["2-Edge Connectivity in Directed Graphs"],"prefix":"10.1145","volume":"13","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[{"name":"University of Ioannina, Ioannina, Greece"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Roma, Italy"}]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[{"name":"\u201cSapienza\u201d Universit\u00e0 di Roma, Roma, Italy"}]},{"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Roma, Italy"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317263"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-3886-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070693217"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065887.1065888"},{"key":"e_1_2_1_5_1","unstructured":"T. H. Cormen C. E. Leiserson and R. L. Rivest. 1991. Introduction to Algorithms. MIT Press Cambridge MA. T. H. Cormen C. E. Leiserson and R. L. Rivest. 1991. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789813.2789828"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01099359"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_18"},{"key":"e_1_2_1_9_1","unstructured":"D. R. Ford and D. R. Fulkerson. 2010. Flows in Networks. Princeton University Press Princeton NJ. D. R. Ford and D. R. Fulkerson. 2010. Flows in Networks. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.10.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764909"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_2_1_13_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co. New York NY. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co. New York NY."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_49"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_49"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_15"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. 862--871","author":"Georgiadis L."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764913"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/dac.612"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_58"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90016-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2015001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"H. Nagamochi and T. Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity 1st ed. Cambridge University Press. 10.1017\/CBO9780511721649 H. Nagamochi and T. Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity 1st ed. Cambridge University Press. 10.1017\/CBO9780511721649","DOI":"10.1017\/CBO9780511721649"},{"key":"e_1_2_1_29_1","unstructured":"H. Nagamochi and T. Watanabe. 1993. Computing k-edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E76A 4 513--517. H. Nagamochi and T. Watanabe. 1993. Computing k-edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E76A 4 513--517."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2968448","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,23]],"date-time":"2021-04-23T22:16:39Z","timestamp":1619216199000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,21]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,12,21]]}},"alternative-id":["10.1145\/2968448"],"URL":"http:\/\/dx.doi.org\/10.1145\/2968448","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2016,12,21]]}}}