{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T02:28:27Z","timestamp":1790562507812,"version":"4.1.0"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","award":["HFRI-FM17-431"],"award-info":[{"award-number":["HFRI-FM17-431"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>In this paper, we investigate some basic connectivity problems in directed graphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, and let $G\\setminus e$ (resp., $G\\setminus v$) be the digraph obtained after deleting edge $e$ (resp., vertex $v$) from $G$. As a first result, we show how to compute in $O(m+n)$ worst-case time: the total number of strongly connected components in $G\\setminus e$ (resp., $G\\setminus v$) for all edges $e$ (resp., for all vertices $v$) in $G$. Let $G$ be strongly connected. We say that edge $e$ (resp., vertex $v$) separates two vertices $x$ and $y$ if $x$ and $y$ are no longer strongly connected in $G\\setminus e$ (resp., $G\\setminus v$). As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: report in $O(n)$ worst-case time all the strongly connected components of $G\\setminus e$ (resp., $G\\setminus v$) for a query edge $e$ (resp., vertex $v$); test whether an edge or a vertex separates two query vertices in $O(1)$ worst-case time; report all edges (resp., vertices) that separate two query vertices in optimal worst-case time, i.e., in time $O(k)$, where $k$ is the number of separating edges (resp., separating vertices). (For $k=0$, the time is $O(1).$) All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by the 1-connectivity (i.e., 1-edge and 1-vertex) cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$ edges that maintains the 1-connectivity cuts of $G$ and the decompositions induced by those cuts.<\/jats:p>","DOI":"10.1137\/19m1258530","type":"journal-article","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T15:00:43Z","timestamp":1598972443000},"page":"865-926","source":"Crossref","is-referenced-by-count":13,"title":["Strong Connectivity in Directed Graphs under Failures, with Applications"],"prefix":"10.1137","volume":"49","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3888-7391","authenticated-orcid":true,"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,9,1]]},"reference":[{"key":"atypb1","unstructured":"A. V. Aho and J. D. Ullman,\n                      The Theory of Parsing, Translation, and Compiling. Volume 2: Compiling\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1972,https:\/\/dl.acm.org\/doi\/10.5555\/578789."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317263"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.08.016"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0452-3"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236730"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10588-006-7084-x"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/070693217"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/3341731"},{"key":"atypb9","unstructured":"M. Cairo, R. Rizzi, A. I. Tomescu, and E. C. Zirondelli,\n                      From Omnitigs to Macrotigs: A Linear-Time Algorithm for Safe Walks-Common to all Closed Arc-Coverings of a Directed Graph\n                      ,https:\/\/arxiv.org\/abs\/2002.10498, 2020."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Chechik, T. D. Hansen, G. F. Italiano, V. Loitzenbauer, and N. Parotsidis,\n                      Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs\n                      , in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017,https:\/\/doi.org\/10.1137\/1.9781611974782.12.","DOI":"10.1137\/1.9781611974782.124"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.247901"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"W. Di Luigi, L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis,\n                      2-connectivity in directed graphs: An experimental study\n                      , in Proceedings of the 17th Workshop on Algorithm Engineering and Experiments, 2015, pp. 173-187,https:\/\/doi.org\/10.1137\/1.9781611973754.15.","DOI":"10.1137\/1.9781611973754.15"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2170849"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01099359"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.10.003"},{"key":"atypb18","unstructured":"H. N. Gabow,\n                      A Poset Approach to Dominator Computation\n                      , Unpublished manuscript, 2013."},{"key":"atypb19","unstructured":"L. Georgiadis, T. D. Hansen, G. F. Italiano, S. Krinninger, and N. Parotsidis,\n                      Decremental data structures for connectivity and dominators in directed graphs\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, eds., LIPIcs Leibniz Int. Proc. Inform. 80, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany, 2017, pp. 42:1-42:15,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.42."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.015"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, G. F. Italiano, A. Karanasiou, N. Parotsidis, and N. Paudel,\n                      Computing2-connected components and maximal 2-connected subgraphs in directed graphs: An experimental study\n                      , in Proceedings 20th Workshop on Algorithm Engineering and Experiments, 2018, pp. 169-183,https:\/\/doi.org\/10.1137\/1.9781611975055.15.","DOI":"10.1137\/1.9781611975055.15"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.007"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"L. Georgiadis, G. F. Italiano, and N. Parotsidis,\n                      Incremental strong connectivity and 2-connectivity in directed graphs\n                      , in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, 2018.","DOI":"10.1007\/978-3-319-77404-6_39"},{"key":"atypb25","first-page":"1","author":"Georgiadis L.","year":"2016","journal-title":"Proceedings of ICALP"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2764913"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0036321"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"atypb29","first-page":"713","author":"Henzinger M.","year":"2015","journal-title":"Proceedings of ICALP"},{"key":"atypb30","unstructured":"M. Henzinger, A. Lincoln, S. Neumann, and V. V. Williams,\n                      Conditional Hardness for Sensitivity Problems\n                      , in Proceedings of the 8th Innovations in Theoretical Computer Science Conference, C. H. Papadimitriou, ed., LIPIcs Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 26:1-26:31,https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.26."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.011"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2015001"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1883"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.5210\/fm.v7i4.941"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2018.02.002"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/362835.362838"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1080\/00207168808803645"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"M. Mihal\u00e1k, P. Uzna\u0144ski, and P. Yordanov,\n                      Prime factorization of the Kirchhoff polynomial: Compact enumeration of arborescences\n                      , in Proceedings of the 13th Workshop on Analytic Algorithmics and Combinatorics, 2016, pp. 93-105,https:\/\/doi.org\/10.1137\/1.9781611974324.10.","DOI":"10.1137\/1.9781611974324.10"},{"key":"atypb40","unstructured":"H. Nagamochi and T. Watanabe,\n                      Computing k-edge-connected components of a multigraph\n                      , IEICE Trans. Fundam. Electron., Commun. Comput. Sci., E76-A.4 (1993), pp. 513-517."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1145\/3228332"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-015-0010-y"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758773"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1258530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:01:41Z","timestamp":1787338901000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1258530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1258530"],"URL":"https:\/\/doi.org\/10.1137\/19m1258530","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}