, |H(u)| into a list L. The algorithm then processed the triples in L, and computes the number of common descendants for each strong bridge. Thus, it is sufficient to replace H(u) with the number of ordinary vertices in H(u)
, Given the dominator trees D and D R , the loop nesting trees H and H R , and the common bridges of G
, After the refine operation in Line 12, a component B = S ? {x} will be created. The fact that x, y ? H(z) implies z ? c(w). Therefore, the nearest common ancestor of x and y in H is also a child of w, so u is not removed from B in Line 18. By the symmetric arguments we have that x and y are also not separated into different components during the pass in the reverse direction. We prove now that if x and y are not vertex-resilient then they will be located in different components at the end of the algorithm
, If x and y are neither siblings nor one is the parent of the other in D or D R , then by Corollary 7.3 they are not vertex-resilient. So x and y are correctly placed in different components during the initialization in Lines 6-7. Thus, we assume that x and y are either siblings of one is the parent of the other
, Suppose, without loss of generality, that y = d(x)
, Suppose x and y are siblings. In this case, x and y will be in separate sets in the collection S computed in Line 11, so they will be placed in different components after the execution of the refine operation in Line 12. Now suppose x = d(y). Then, the nearest common ancestor of y and x in H is not a proper descendant of w, different strongly connected components in G \ w. So, by Lemma 6.3, x and y cannot be in the same subtree H(z)
, Let D and H be the dominator tree and the loop nesting forest, respectively, of a flow of d(x) in T , then clearly d(x) is not a proper dominator of h(x)
, Let y be the child of d(x) that is an ancestor of h(x) in D. Since h(x) is not a sibling of x in D, y = h(x). Also, y = x by the fact that h(x) is a proper ancestor of x in T . Then, Lemma 2.5 implies that ? contains y, so y ? H(h(x)). But since y is a proper dominator of h(x), it is a proper ancestor of h(x) in T , a contradiction, By the definition of h(x), there is a path ? in G s from x to h(x) such that, for all vertices x in ?, x ? H(h(x))
, Corollary 7.10. Let D and H be the dominator tree and the loop nesting forest, respectively
, Theorem 7.11. Algorithm HDVRC runs in O(m + n) time, or in O(n) time if the dominator trees D and D R , and the loop nesting trees H and H R are given as input
, Line 26), this is done by iterating over the adjacency list of each vertex v ? c(u) (resp., v ? c R (u)) in the component forest F , and marking the component nodes that are visited at least twice. Now we bound the total number of vertices and nodes that we traverse in the component forest during this process. During the foreach loop in the "forward" (resp., "reverse") direction, we traverse every adjacency list of a vertex v at most twice, The initialization, including the computation of the G R , takes O(m + n) time. The computation of the dominator and loop nesting trees also takes O(m+n) time by
, While we are processing u, we find its children x that satisfy the condition h(x) ?
, )|). Thus, by Lemma 7.7, each refine operation in Lines 11 and 27 takes time O(|c(u)|) and O(|c R (u)|), respectively, which is O(n) in total. Finally, since the component forest contains at most n ? 1 components at any given time, the loops in Lines 14-21 and 30-37 execute at most 2(n?1) nearest common ancestor (nca) calculations, For each such child x, we do a preorder traversal H(x) as follows. When we are at a vertex x we visit only the children of x in H that are siblings of x in D. By Corollary 7.10, a vertex is in H(x) ? c(u) if and only if it is visited during this traversal of H(x)
, We remark that we can extend Algorithm HDVRC in the same way as for HD2ECC (see Section
, All our bounds are asymptotically tight. Our work raises some new and perhaps intriguing questions. First, using the algorithmic framework developed in this paper, we can find in linear time an edge or a vertex whose removal minimizes/maximizes several properties of the resulting strongly connected components, such as their number, or their largest or their smallest size. Can our approach be used to find in linear time an edge (resp., a vertex) whose removal optimizes some more complex properties of the resulting strongly connected components? In particular, can we find an edge e (resp., a vertex v) that minimizes/maximizes a given function f (|C 1 |, |C 2 |, We have presented a collection of O(n)-space data structures that, after O(m + n)-time preprocessing, can solve efficiently several problems, including reporting in O(n) worst-case time all the strongly connected components obtained after deleting a single edge (resp
, The Theory of Parsing, Translation, and Compiling, vol.2, 1972.
, Dominators in linear time, SIAM Journal on Computing, vol.28, issue.6, pp.2117-2149, 1999.
, Detecting critical nodes in sparse graphs, Comput. Oper. Res, vol.36, issue.7, pp.2193-2200, 2009.
, Counterexamples for directed and node capacitated cut-trees, SIAM Journal on Computing, vol.24, pp.505-510, 1995.
, Identifying sets of key players in a social network, Computational & Mathematical Organization Theory, vol.12, issue.1, pp.21-34, 2006.
, Linear-time algorithms for dominators and other path-evaluation problems, SIAM Journal on Computing, vol.38, issue.4, pp.1533-1573, 2008.
, Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs, Proc. 28th ACM-SIAM Symp. on Discrete Algorithms, pp.1900-1918, 2017.
, Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett, vol.91, p.247901, 2003.
, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems, vol.13, issue.4, pp.451-490, 1991.
, Oracles for distances avoiding a failed node or link, SIAM Journal on Computing, vol.37, issue.5, pp.1299-1318, 2008.
, 2-connectivity in directed graphs: An experimental study, Proc. 17th Workshop on Algorithm Engineering and Experiments, pp.173-187, 2015.
, On new approaches of assessing network vulnerability: Hardness and approximation, IEEE/ACM Transactions on Networking, vol.20, issue.2, pp.609-619, 2012.
, Bijoin points, bibridges, and biblocks of directed graphs, Cybernetics, vol.16, issue.1, pp.41-44, 1980.
, Finding dominators via disjoint set union, Journal of Discrete Algorithms, vol.23, pp.2-20, 2013.
, A poset approach to dominator computation. Unpublished manuscript, 2013.
, Decremental data structures for connectivity and dominators in directed graphs, Proc. 44th Int'l. Coll. on Automata, Languages, and Programming, vol.42, p.15, 2017.
, Sparse certificates for 2-connectivity in directed graphs, Strings and Theoretical Approaches in the Big Data Era, vol.698, pp.40-66, 2017.
, Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: An experimental study, Proc. 20th Workshop on Algorithm Engineering and Experiments, pp.169-183, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01925963
, 2-edge connectivity in directed graphs, ACM Transactions on Algorithms, vol.13, issue.1, pp.1-9, 2015.
, 2-vertex connectivity in directed graphs, Information and Computation, vol.261, issue.2, pp.248-264, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01925966
, Incremental 2-edge-connectivity in directed graphs, Proc. 43rd Int'l. Coll. on Automata, Languages, and Programming, vol.49, p.15, 2016.
, Incremental strong connectivity and2-connectivity in directed graphs, Proc. 13th Latin American Symp. on Theoretical Informatics, pp.529-543, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01925953
, Dominator tree certification and divergent spanning trees, ACM Transactions on Algorithms, vol.12, issue.1, 2015.
, A linear framework for time-scale separation in nonlinear biochemical systems, PLoS ONE, vol.7, issue.5, p.36321, 2012.
, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, vol.13, issue.2, pp.338-55, 1984.
, Finding 2-edge and 2-vertex strongly connected components in quadratic time, Proc. 42nd Int'l. Coll. on Automata, Languages, and Programming, pp.713-724, 2015.
, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science, vol.447, pp.74-84, 2012.
, Computing the 2-blocks of directed graphs, RAIRO-Theoretical Informatics and Applications, vol.49, issue.2, pp.93-119, 2015.
, A fully dynamic algorithm for maintaining the transitive closure, Journal of Computer and System Sciences, vol.65, issue.1, pp.150-167, 2002.
, Uncloaking terrorist networks, First Monday, vol.7, issue.4, 2002.
, The critical node detection problem in networks: A survey, Computer Science Review, vol.28, pp.92-117, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01883783
, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems, vol.1, issue.1, pp.121-162, 1979.
, Object code optimization, Communications of the ACM, vol.12, issue.1, pp.13-22, 1969.
, An algorithm for finding all the k-components of a digraph, Int. Journal of Computer Mathematics, vol.24, issue.3-4, pp.213-221, 1988.
, Prime factorization of the kirchhoff polynomial: Compact enumeration of arborescences, Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics, pp.93-105, 2016.
, Computing k-edge-connected components of a multigraph, E76-A, vol.4, pp.513-517, 1993.
, Computing critical nodes in directed graphs, ACM Journal of Experimental Algorithmics, vol.23, issue.2, p.24, 2018.
, Depth-first search and linear graph algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972.
, Finding dominators in directed graphs, SIAM Journal on Computing, vol.3, issue.1, pp.62-89, 1974.
, Efficiency of a good but not linear set union algorithm, Journal of the ACM, vol.22, issue.2, pp.215-225, 1975.
, Edge-disjoint spanning trees and depth-first search, Acta Informatica, vol.6, issue.2, pp.171-85, 1976.
, Efficiently identifying critical nodes in large complex networks, Computational Social Networks, vol.2, issue.1, 2015.
, Maintaining bridge-connected and biconnected components on-line, Algorithmica, vol.7, issue.5&6, pp.433-464, 1992.