2-vertex connectivity in directed graphs. (English) Zbl 1395.68209
Summary: Given a directed graph, two vertices \(v\) and \(w\) are 2-vertex-connected if there are two internally vertex-disjoint paths from \(v\) to \(w\) and two internally vertex-disjoint paths from \(w\) to \(v\). In this paper, we show how to compute this relation in \(O(m + n)\) time, where \(n\) is the number of vertices and \(m\) is the number of edges of the graph. As a side result, we show how to build in linear time an \(O(n)\)-space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices \(v\) and \(w\) are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from \(v\) to \(w\) or in all paths from \(w\) to \(v\).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C40 | Connectivity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68P05 | Data structures |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alstrup, S.; Harel, D.; Lauridsen, P. W.; Thorup, M., Dominators in linear time, SIAM J. Comput., 28, 6, 2117-2132, (1999) · Zbl 0939.68158 |
| [2] | 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 J. Comput., 38, 4, 1533-1573, (2008) · Zbl 1181.05079 |
| [3] | Buchsbaum, A. L.; Kaplan, H.; Rogers, A.; Westbrook, J. R., A new, simpler linear-time dominators algorithm, ACM Trans. Program. Lang. Syst., ACM Trans. Program. Lang. Syst., 27, 3, 383-387, (2005), Corrigendum in |
| [4] | Fraczak, W.; Georgiadis, L.; Miller, A.; Tarjan, R. E., Finding dominators via disjoint set union, J. Discret. Algorithms, 23, 2-20, (2013) · Zbl 1294.05148 |
| [5] | Gabow, H. N., The minset-poset approach to representations of graph connectivity, ACM Trans. Algorithms, 12, 2, 24:1-24:73, (February 2016) · Zbl 1398.05198 |
| [6] | Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, J. Comput. Syst. Sci., 30, 2, 209-221, (1985) · Zbl 0572.68058 |
| [7] | Georgiadis, L.; Italiano, G. F.; Laura, L.; Parotsidis, N., 2-edge connectivity in directed graphs, ACM Trans. Algorithms, 13, 1, 9:1-9:24, (2016), Announced at SODA15 · Zbl 1451.05092 |
| [8] | Georgiadis, L.; Tarjan, R. E., Dominator tree certification and divergent spanning trees, ACM Trans. Algorithms, 12, 1, 11:1-11:42, (November 2015) · Zbl 1398.68396 |
| [9] | Henzinger, M.; Krinninger, S.; Loitzenbauer, V., Finding 2-edge and 2-vertex strongly connected components in quadratic time, (Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), (2015)) · Zbl 1410.05203 |
| [10] | Italiano, G. F.; Laura, L.; Santaroni, F., Finding strong bridges and strong articulation points in linear time, Theor. Comput. Sci., 447, 74-84, (2012) · Zbl 1245.05128 |
| [11] | Jaberi, R., Computing the 2-blocks of directed graphs, RAIRO Theor. Inform. Appl., 49, 2, 93-119, (2015) · Zbl 1342.05055 |
| [12] | Jaberi, R., On computing the 2-vertex-connected components of directed graphs, Discrete Appl. Math., 204, 164-172, (2016) · Zbl 1333.05136 |
| [13] | Lengauer, T.; Tarjan, R. E., A fast algorithm for finding dominators in a flowgraph, ACM Trans. Program. Lang. Syst., 1, 1, 121-141, (1979) · Zbl 0449.68024 |
| [14] | Di Luigi, W.; Georgiadis, L.; Italiano, G. F.; Laura, L.; Parotsidis, N., 2-connectivity in directed graphs: an experimental study, (Proc. 17th Workshop on Algorithm Engineering and Experiments, (2015)), 173-187 · Zbl 1430.05125 |
| [15] | Menger, K., Zur allgemeinen kurventheorie, Fundam. Math., 10, 96-115, (1927) · JFM 53.0561.01 |
| [16] | Nagamochi, H.; Watanabe, T., Computing k-edge-connected components of a multigraph, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E76A, 4, 513-517, (1993) |
| [17] | Reif, J. H.; Spirakis, P. G., Strong k-connectivity in digraphs and random digraphs, (1981), Harvard University, Technical Report TR-25-81 |
| [18] | Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160, (1972) · Zbl 0251.05107 |
| [19] | Tarjan, R. E., Finding dominators in directed graphs, SIAM J. Comput., 3, 1, 62-89, (1974) · Zbl 0296.68030 |
| [20] | Tarjan, R. E., Efficiency of a good but not linear set union algorithm, J. ACM, 22, 2, 215-225, (1975) · Zbl 0307.68029 |
| [21] | Westbrook, J.; Tarjan, R. E., Maintaining bridge-connected and biconnected components on-line, Algorithmica, 7, 5&6, 433-464, (1992) · Zbl 0748.68045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
