Problems related to strong connectivity and strong biconnectivity

Raed Jaberi

June 15, 2026

Abstract

Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. In this paper we study the problem of computing a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and for each vertex \(w \in B\), the subgraph \(G_{\beta} \setminus \lbrace w\rbrace\) is strongly connected. We prove that there exists a polynomial time \(7\)-approximation algorithm for this problem.

Algorithms ,Graph connectivity ,Directed graphs,strongly connected graph

1 Introduction↩︎

Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. In this paper we study the problem of computing a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and for each vertex \(w \in B\), the subgraph \(G_{\beta} \setminus \lbrace w\rbrace\) is strongly connected. Note that the minimum strongly biconnected spanning subgraph problem is a special case of this problem when \(B=\emptyset\) [1]. Therefore, this problem is NP-complete.

The problem of calculating a strongly connected spanning subgraph with minimum number of edges is NP-complete [2], [3]. In \(1994\), Khuller et al.[3] gave an approximation algorithm for the minimum strongly connected spanning subgraph problem. In \(2001\), Vetta [4] presented a polynomial time approximation algorithms of an approximation ratio of \(3/2\). Moreover, in \(2003\), Zhao et al. [5] developed a linear time \(5/3\)-approximation for the minimum strongly-connected spanning subgraph problem. The problem of finding strongly connected components in directed graph has been thoroughly investigated and solved by efficient linear time algorithms [6]–[14]. Wu and Grumbach [15] introduced the concept of strongly biconnected directed graph and strongly biconnected components. The problem of computing a strongly biconnected spanning subgraph with minimum number of edges is NP-complete and has been studied by Jaberi in \(2022\) [1]. Many concepts and problems related to strong connectivity, strong biconnectivity and twinless strong connectivity in directed graphs have received considerable attention in [15]–[30]. \(k\)-vertex-connected and \(k\)-edge connected graphs have many useful properties [31]–[33]. Testing wheteher undirected graph is \(2\)-vertex connected and finding bridges, articulation points and biconnected components can be done in linear time [6], [10], [34]–[37]. Testing whether a directed graph is \(2\)-vertex connected can be done in linear time [38]. Strong articulation points and strong bridges can be identified in linear time using efficient algorithms presented by Italiano et al. [39]–[41]. These efficient algorithms are based on a close relationship between strong articulation points, strong bridges and dominators in flowgraphs. The problem of finding dominators can be solved efficiently in flowgraphs [42]–[47]. Carmesin et al. studied \(k\)-blocks in undirected graphs [48]. Makino [49] and Reif et al. [50] studied \(k\)-components in directed graphs. The problem of computing \(2\)-connected components and \(2\)-blocks in directed graphs have been extensively studied in [21], [26], [51]–[63].

Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. In this paper we study the problem of computing a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and for each vertex \(w \in B\), the subgraph \(G_{\beta} \setminus \lbrace w\rbrace\) is strongly connected. We will denote this problem by MBSC. We prove that there exists a polynomial time \(7\)-approximation algorithm for MBSC

2 A special case where all cervices in \(V\setminus B\) are strong articulation points↩︎

In \(2015\), Jaberi [52] proved that there is an approximation algorithm with approximation factor \(17/3\) for the minimum strongly connected spanning subgraph with the same strong articulation points. His proof is based on the results of Georgiadis [38], Italiano [39], and Zhao et al. [5].

Example 1 shows that an optimal solution for the minimum strongly connected spanning subgraph with the same strong articulation points is not necessarily an optimal solution for MBSC.

Figure 1: (a) Each vertex in V\setminus \lbrace 3,9,6 \rbrace is a strong articulation point. (b) An optimal solution for minimum strongly connected spanning subgraph problem with same strong articulation points. (c) An optimal solution for MBSC when B=\lbrace 9 \rbrace.

Moreover, Example 2 shows that an optimal solution for the minimum strongly connected spanning subgraph problem is not necessarily an optimal solution for MBSC.

Figure 2: (a) Each vertex in V\setminus \lbrace 3,9 \rbrace is a strong articulation point. (b) An optimal solution for minimum strongly connected spanning subgraph problem.(c) An optimal solution when B=\lbrace 3 \rbrace.

Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. If each vertex in \(V\setminus B\) is a strong articulation point, then by results of Jaberi [52], there is an approximation algorithm with approximation factor \(17/3\) for MBSC in this special case.

3 Approximation algorithm for MBSC↩︎

In this section, we prove that there is a \(7\)-approximation algorithm for MBSC. Algorithm 3 is an approixmation algorithm for MBSC. This algorithms is based on [39] ,independent spanning trees [44], and the results of Georgiadis et al. [64]–[66].

None

Figure 3: No caption.

Lemma 1 shows that the output of Algorithm 3 is a feasible solution for MBSC.

Lemma 1. Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. Let \(G_{\beta}=(V,E_{\beta} )\) be the output of the Algorithm 3. Then, \(G_{\beta}=(V,E_{\beta} )\) is strongly biconnected and for each vertex \(w \in B\), \(w\) is not a strong articulation point.

Proof. We consider three cases:

  • Case \(1\). \(B=V\). In this case, \(G_{\beta}=(V,E_{\beta} )\) is a minimal \(2\)-vertex connected spanning subgraph of \(G\). Since the subgraph \(G_{\beta}=(V,E_{\beta} )\) is \(2\)-vertex connected, \(G_{\beta}=(V,E_{\beta} )\) has no strong articulation points. Moreover, \(G_{\beta}=(V,E_{\beta} )\) is strongly biconnected because its underlying graph is biconnected.

  • Case \(2\). \(|B|=0\). In this case. each feasible solution for minimum strongly biconnected spanning subgrpah problem is a feasible solution for MBSC beacuse minimum strongly biconnected spanning subgraph problem is a special case of MBSC when \(B\) does not contain any vertex..

  • Case \(3\). \(|B|>0\) and \(|B|<n\). Since \(E_{1}\subseteq E_{\beta}\),the subgraph \(G_{\beta}=(V,E_{\beta} )\) is strongly biconnected. Now we need to ensure that none of the vertices in \(B\) is a strong articulation point of the subgraph \(G_{\beta}=(V,E_{\beta} )\). We consider two subcases:

    1. Case \(3(a)\). \(|B|=1\) and \(B \neq V\). Let \(B=\lbrace s \rbrace\). The subgraph \((V\setminus \lbrace s \rbrace,E_{2})\) is strongly connected and \(E_{2}\subseteq E_{\beta}\). Therefore. the vertex \(s\) is not a strong articulation point of \(G_{\beta}=(V,E_{\beta} )\).

    2. Case \(3(b)\). \(|B|>1\) and \(|B|\neq V\). By [39] and the properties of two independent tree [44], [66], each vertex in \(B\) is not a strong articulation point of \(G_{\beta}=(V,E_{\beta} )\).

 ◻

Let \(E_{O}\) be an optimal solution for MBSC. Since the subgraph \((V,E_{O})\) is strongly biconnected, the subgraph \((V,E_{O})\) is strongly connected and hence \(|E_{O}|\geq n\). The following theorem shows that Algorithm 3 has an approximation ratio of \(7\).

Theorem 1. Let \(G_{\beta}=(V,E_{\beta} )\) be the output of the Algorithm 3. Then \(|E_{\beta}|\leq 7n-4\).

Proof. Let \(G=(V,E)\) be a strong biconnected graph and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. Let \(G_{\beta}=(V,E_{\beta} )\) be the output of the Algorithm 3. We consider three cases:

  • Case \(1\). \(B=V\). In this case, the directed graph \(G=(V,E)\) is \(2\)-vertex connected since no vertex in \(B\) is a strong articulation point of \(G\). The output \(G_{\beta}=(V,E_{\beta})\) is a minimal \(2\)-vertex connected spanning subgraph of \(G\). Results of Edmonds [67] and Mader [33] imply that \(|E_{\beta}| \leq 4n\) [66], [68].

  • Case \(2\). \(B\) contains no vertices. In this case. each solution for minimum strongly biconnected spanning subgrpah problem is a solution for MBSC. Therefore, \(|E_{\beta}| \leq 3n\) [23].

  • Case \(3\). \(|B|>0\) and \(|B|<n\). In this case we have \(|E_{1}| \leq 3n\) [23].We consider two subcases:

    1. Case \(3(a)\). \(|B|=1\) and \(B\neq V\). Note that \(E_{2}\) consists of two spanning trees. Thus, we \(|E_{2}|\leq 2(n-2)\).

    2. Case \(3(b)\). \(|B|>1\) and \(|B|\neq V\). Note that \(E_{2}\) consists of two independent trees and \(E_{3}\) consists of two independent trees. Therefore, we have \(|E_{2}\cup E_{3}|\leq 4n-4\).

 ◻

The following theorem shows that Algorithm 3 runs in polynomial time.

Theorem 1. The running time of Algorithm 3 is \(O(nm)\).

Proof. if \(B=V\), then the input graph is \(2\)-vertex connected. A minimal \(2\)-vertex-connected subgraph of a \(2\)-vertex connected directed graph can be found in time \(O(n^2)\) [64], [66]. Therefore, line \(2\) takes time \(O(n^2)\). Moreover, a minimal strongly biconnected spanning subgraph of a strongly biconnected directed graph can be computed in time \(O(nm)\) [1]. A spanning tree in directed graphs can be found in linear time using DFS or BFS. Non tirival dominators and two independent spanning trees of a flow graph can be identified in \(O(n+m)\) time. [44], [66]. ◻

4 Additional problems related to strong connectivity amd strong biconnectivity↩︎

In this section we describe additional problems related to strong connectivity and strong biconnectivity.

Problem 2. Let \(G=(V,E)\) be a strong biconnected graph, let \(i\) be an integer, and let \(B \subseteq V\) such that for each vertex \(w \in B\), the subgraph \(G \setminus \lbrace w\rbrace\) is strongly connected. The goal is to compute a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and \(|\lbrace v\mid v\in B \text{ and } v \text{ not a strong articulation point of } G_{\beta} \rbrace|\geq i\).

Problem 3 is a special case of the minimum 2-vertex connected spanning subgraph problem when \(B=V\) and \(i=n\). Algorithm 3 is a polynomial time approximation algorithm with approximation factor \(7\) for this problem.

Problem 3. Let \(G=(V,E)\) be a \(2\)-vertex strongly biconnected graph [22] and let \(i\) be an integer. The goal is to compute a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and the number of strong articulation point of this subgraph is at most \(i\).

This problem is NP-complete because the minimum \(2\)-vertex connected spanning subgraph problem is a special case of this problem when \(i=0\). Note that an optimal solution for the minimum strongly connected spanning subgraph problem is not necessarily an optimal solution for this problem. Furthermore, an optimal solution for the minimum \(2\)-vertex strongly biconnected spanning subgraph problem is not necessarily an optimal solution for this problem. Algorithm 3 can be modified in order to obtain a polynomial time approximation algorithm with approximation factor \(7\).

Problem 4. Let \(G=(V,E)\) be a \(2\)-vertex strongly biconnected graph [22] and let \(i\) be an integer. The goal is to compute a subset \(E_{\beta} \subseteq E\) of minimum size such that the subgraph \(G_{\beta}=(V,E_{\beta})\) is strongly biconnected and the number of b-articulation point of this subgraph is at most \(i\).

The minimum \(2\)-vertex strongly biconnected spanning subgraph problem is a special case of Problem 4 when \(i=0\). Therefore, Problem 4 is NP-complete. Note that an optimal solution for the minimum strongly connected spanning subgraph problem is not necessarily an optimal solution for this problem. Furthermore, an optimal solution for the minimum \(2\)-vertex strongly biconnected spanning subgraph problem is not necessarily an optimal solution for this problem.

References↩︎

[1]
Raed Jaberi, Minimum strongly biconnected spanning directed subgraph problem. CoRR abs/2207.04321 (2022).
[2]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman \(1979\), ISBN \(0\)–\(7167\)–\(1044\)–\(7\).
[3]
S. Khuller, B. Raghavachari, N.E. Young, Approximating the Minimum Equivalent Diagraph. SODA \((1994)\)\(177\)–\(186\).
[4]
Adrian Vetta: Approximating the minimum strongly connected subgraph via a matching lower bound. SODA \(417\)–\(426(2001)\).
[5]
L. Zhao, H. Nagamochi, T. Ibaraki, A linear time \(5/3\)-approximation for the minimum strongly-connected spanning subgraph problem, Inf. Process. Lett. \(86\)(\(2003\)) \(63\)–\(70\).
[6]
R. E. Tarjan, Depth First Search and Linear Graph Algorithms, SIAM J. Comput.,\(1(2) (1972),146\)–\(160\).
[7]
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1999). Data structures and algorithms. Addison-Wesley series in computer science and information processing (Repr. with corrections ed.). Reading, Mass.: Addison-Wesley. ISBN 978-0-201-00023-8.
[8]
M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers and Mathematics with Applications, \(7(1):67\)–\(72, (1981)\).
[9]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed. Cambridge: The MIT Press, 2022.
[10]
Harold N. Gabow: Path-based depth-first search for strong and biconnected components. Inf. Process. Lett. 74(3-4): 107-114 (2000).
[11]
Joseph Cheriyan, Kurt Mehlhorn: Algorithms for Dense Graphs and Networks on the Random Access Computer. Algorithmica 15(6): \(521\)–\(549(1996)\).
[12]
Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer \(2019\), ISBN 978-3-030-25208-3, page \(292\).
[13]
Esko Nuutila, Eljas Soisalon-Soininen: On Finding the Strongly Connected Components in a Directed Graph, Inf. Process. Lett. \(49(1): 9\)–\(14 (1994)\).
[14]
David J. Pearce: A space-efficient algorithm for finding strongly connected components, Inf. Process. Lett., \(116(1)47\)–\(52(2016)\).
[15]
Z. Wu, S. Grumbach, Feasibility of motion planning on acyclic and strongly connected directed graphs. Discret. Appl. Math. \(158(9): 1017\)–\(1028 (2010)\).
[16]
Adi Botea, Davide Bonusi, Pavel Surynek: Solving Multi-agent Path Finding on Strongly Biconnected Digraphs. J. Artif. Intell. Res.\(62: 273\)–\(314 (2018)\).
[17]
Adi Botea, Davide Bonusi, Pavel Surynek: Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract). IJCAI \(5563\)–\(5567(2018)\).
[18]
Adi Botea, Pavel Surynek: Multi-Agent Path Finding on Strongly Biconnected Digraphs. AAAI \(2015: 2024\)–\(2030\).
[19]
S. Raghavan, Twinless Strongly Connected Components, Perspectives in Operations Research, (\(2006\)) \(285\)–\(304\).
[20]
Raed Jaberi, Twinless articulation points and some related problems. CoRR abs/1912.11799 \((2019)\).
[21]
Raed Jaberi, Computing 2-twinless blocks, Discrete Mathematics Letters, \(29\)–\(33\), Volume \(5 (2021)\), DOI: 10.47443/dml.2020.0037.
[22]
Raed Jaberi, Minimum 2-Vertex Strongly Biconnected Spanning Directed Subgraph Problem Discrete Mathematics Letters, \(40\)–\(43\), Volume \(7(2021)\) DOI: 10.47443/dml.2021.0024.
[23]
Raed Jaberi, Minimum 2-edge strongly biconnected spanning directed subgraph problem, CoRR abs/2207.03401 \((2022)\).
[24]
Raed Jaberi, b-articulation points and b-bridges in strongly biconnected directed graphs. CoRR abs/2007.01897 \((2020)\).
[25]
Loukas Georgiadis, Evangelos Kosinas, Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. ISAAC \(2020\)\(38:1\)–\(38:16\).
[26]
Raed Jaberi, 2-blocks in strongly biconnected directed graphs. CoRR abs/2007.09793 \((2020)\).
[27]
Raed Jaberi, Minimum \(2\)-vertex-twinless connected spanning subgraph problem. CoRR abs/2001.03788 (2020).
[28]
Raed Jaberi, Reham Mansour, An experimental study of algorithms for identifying approximate solutions for minimum 2-T connected spanning subgraph problem, Homs University Journal \(2026\).
[29]
Olivier Durand de Gevigney, Zoltán Szigeti: On minimally \(2\)-T-connected directed graphs. Discret. Appl. Math. \(250: 183\)–\(185 (2018)\).
[30]
Loukas Georgiadis and Evangelos Kosinas. Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.38.
[31]
Menger, Karl, "Zur allgemeinen Kurventheorie". Fund. Math. \((1927) 10: 96\)–\(115\). doi:10.4064/fm-10-1-96-115.
[32]
W. Mader, A reduction method for edge-connectivity in graphs, Ann. Disc. Math. \((1978) 145\)–\(164\).
[33]
W. Mader, Minimal \(n\)-fach zusammenhängende Digraphen. J. Comb. Theory, Ser. B \(38(2): 102\)–\(117 (1985)\).
[34]
Jens M. Schmidt: A simple test on \(2\)-vertex- and \(2\)-edge-connectivity. Inf. Process. Lett. \(113(7): 241\)-\(244 (2013)\).
[35]
U. Brandes. Eager st-Ordering. In Proceedings of the 10th European Symposium of Algorithms (ESA’02), pages 247–256, 2002.
[36]
J. Ebert. st-Ordering the vertices of biconnected graphs. Computing, 30:19–33, 1983.
[37]
R. E. Tarjan. A note on finding the bridges of a graph. Information Processing Letters, 2(6):160–161, 1974.
[38]
L. Georgiadis, Testing \(2\)-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, In Proc. \(37\)th ICALP, Part I, LNCS \(6198\)(\(2010\)) \(738\)–\(749\).
[39]
G.F. Italiano, L. Laura, F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science \(447\)(\(2012\)) \(74\)–\(84\).
[40]
G. F. Italiano, L. Laura, F. Santaroni, Finding Strong Bridges and Strong Articulation Points in Linear Time. COCOA \((1) 2010: 157\)–\(169\).
[41]
Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Federico Santaroni: Strong Articulation Points and Strong Bridges in Large Scale Graphs. Algorithmica \(74(3)\): \(1123\)–\(1147 (2016)\).
[42]
A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan, J.R. Westbrook, Linear-time algorithms for dominators and other path-evaluation problems, SIAM J. Comput. \(38\)(\(4\)) (\(2008\)) \(1533\)–\(1573\).
[43]
Loukas Georgiadis, Robert E. Tarjan, Dominator Tree Certification and Divergent Spanning Trees. ACM Trans. Algorithms \(12(1): 11:1\)–\(11:42 (2016)\).
[44]
Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. \(433\)–\(442 (2005)\).
[45]
T. Lengauer, R.E. Tarjan, A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. \(1(1)\)(\(1979\)) \(121\)–\(141\).
[46]
S. Alstrup, D. Harel, P.W. Lauridsen, M. Thorup, Dominators in linear time, SIAM J. Comput. \(28\)(\(6\)) (\(1999\)) \(2117\)–\(2132\).
[47]
A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan, J.R. Westbrook, Linear-time algorithms for dominators and other path-evaluation problems, SIAM J. Comput. \(38\)(\(4\)) (\(2008\)) \(1533\)–\(1573\).
[48]
Johannes Carmesin, Reinhard Diestel, Matthias Hamann, Fabian Hundertmark: k-Blocks: A Connectivity Invariant for Graphs. SIAM J. Discret. Math. 28(4): 1876-1891 (2014).
[49]
S. Makino An algorithm for finding all the k-components of a digraph Int. J. Comput. Math., 24 (3–4) (1988), pp. 213-221.
[50]
J.H. Reif, P.G. Spirakis Strong k-Connectivity in Digraphs and Random Digraphs, Technical Report TR-25–81 Harvard University (1981).
[51]
Y. M. Erusalimskii and G. G. Svetlov. Bijoin points, bibridges, and biblocks of directed graphs. Cybernetics and Systems Analysis, 16(1):41–44, 1980.
[52]
Raed Jaberi, Computing the 2-blocks of directed graphs. RAIRO - Theor. Inf. and Applic. \(49(2) (2015) 93\)–\(119\).
[53]
Raed Jaberi, On computing the 2-vertex-connected components of directed graphs. Discrete Applied Mathematics 204: \((2016)164\)–\(172\) .
[54]
Raed Jaberi, \(2\)-edge-twinless blocks, Bulletin des Sciences Mathématiques, Volume \(168\), \(102969\), ISSN \(0007\)–\(4497\), \((2021)\), https://doi.org/10.1016/j.bulsci.2021.102969.
[55]
L. Georgiadis, G.F. Italiano, L. Laura, N. Parotsidis, \(2\)-Edge Connectivity in Directed Graphs, SODA (\(2015\)) \(1988\)–\(2005\).
[56]
L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis, \(2\)-Edge Connectivity in Directed Graphs. ACM Trans. Algorithms \(13(1): 9:1\)–\(9:24 (2016)\).
[57]
L. Georgiadis, G.F. Italiano, L. Laura, N. Parotsidis, \(2\)-Vertex Connectivity in Directed Graphs, ICALP \((1)2015: 605\)–\(616\).
[58]
L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis, \(2\)-vertex connectivity in directed graphs. Inf. Comput. \(261: 248\)–\(264 (2018)\).
[59]
L. Georgiadis, G. F. Italiano, A. Karanasiou, N. Parotsidis, N. Paudel, Computing \(2\)-Connected Components and Maximal \(2\)-Connected Subgraphs in Directed Graphs: An Experimental Study. ALENEX \(2018: 169\)–\(183\).
[60]
L. Georgiadis, G.F. Italiano, C. Papadopoulos, N. Parotsidis, Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs, in: Proc. 23rd European Symposium on Algorithms, \(2015\), pp.\(582\)–\(594\).
[61]
Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer: Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. ICALP (1) 2015: \(713\)–\(724\).
[62]
D. Dahiphale, "MapReduce for Graphs Processing: New Big Data Algorithm for 2-Edge Connected Components and Future Ideas," in IEEE Access, vol. 11, pp. 54986-55001, 2023, doi: 10.1109/ACCESS.2023.3281266.
[63]
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis:
[64]
L. Georgiadis, G. F. Italiano, A. Karanasiou: Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. Theor. Comput. Sci. \(807\): \(185\)–\(200 (2020)\).
[65]
L. Georgiadis, G. F. Italiano, A. Karanasiou: Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders,” Proc.16th International Symposium on Experimental Algorithms, pp.9:1-9:16, 2017.
[66]
L. Georgiadis: Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph. ESA \(2011: 13\)–\(24\).
[67]
J. Edmonds, Edge-disjoint branchings. Combinatorial Algorithms, pages \(91\)–\(96\), \(1972\).
[68]
J. Cheriyan, R. Thurimella, Approximating Minimum-Size \(k\)-Connected Spanning Subgraphs via Matching. SIAM J. Comput. 30(2): 528–560 (2000).

Subjects

Data Structures and Algorithms (cs.DS)

Updated on Academus

2026/06/19 16:14 UTC