Computing 2-twinless blocks

Raed Jaberi

doi:10.47443/dml.2020.0037

Author(s)

Raed Jaberi Department of Software and Information Systems, Tishreen University, Lattakia, Syria

Abstract

Let G = (V; E) be a directed graph. A 2-twinless block in G is a maximal subset B V of size at least 2 such that for every pair of distinct vertices x; y 2 B, and for every vertex w 2 V n fx; yg, the vertices x; y are in the same twinless strongly connected component of G n fwg. In this paper, algorithms for computing the 2-twinless blocks of a directed graph are presented.

Publication Details

Page(s) 29-33

DOI 10.47443/dml.2020.0037

Published Journal: Discrete Mathematics Letters, Volume: 5, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

graph algorithms, connectivity, 2-blocks, twinless strongly connected graphs, directed graphs

References

Alstrup S.,Harel D.,Lauridsen P.W.,Thorup M. .1999 .Dominators in linear time. SIAM J. Comput, 28 : 2117-2132.

Buchsbaum A. L.,Georgiadis L.,Kaplan H.,Rogers A.,Tarjan R. E.,Westbrook J. R. .2008 .Linear-time algorithms for dominators and other pathevaluation problems. SIAM J. Comput, 38 : 1533-1573.

Firmani D.,Italiano G. F.,Laura L.,Orlandi A.,Santaroni F.,Experimental Algorithms .2012 .Computing strong articulation points and strong bridges in large scale graphs. SEA 2012, Lecture Notes in Computer Science, 7276 : 195-207.

Firmani D.,Georgiadis L.,Italiano G. F.,Laura L.,Santaroni F. .2016 .Strong articulation points and strong bridges in large scale graphs. Algorithmica, 74 : 1123-1147.

Gavril F. .1972 .Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, : 180-187.

Georgiadis L.,Tarjan R. E.,Werneck R F. .2006 .. J. Graph Algorithms Appl, 10 : 69-94.

Georgiadis L.,Gavoille C.,Kirchner C. .2021 .-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. ICALP 2010, Lecture Notes in Computer Science, 6198 : 738-749.

Georgiadis L. .2020 .Linear-time algorithms for computing twinless strong articulation points and related problems. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC, 38 : 16-38.

Georgiadis L.,Italiano G. F.,Laura L.,Parotsidis N. .2015 .-Edge connectivity in directed graphs. Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms, : 1988-2005.

Georgiadis L.,Italiano G. F.,Laura L.,Parotsidis N. .2016 .-Edge connectivity in directed graphs. ACM Trans. Algorithms, 13 : 9.

Georgiadis L.,Italiano G. F.,Laura L.,Parotsidis N.,Iwama K.,Kobayashi N.,Programming B. .2015 .-Vertex connectivity in directed graphs. ICALP 2015, Lecture Notes in Computer Science, 9134 : 605-616.

Georgiadis L.,Italiano G. F.,Laura L.,Parotsidis N. .2018 .-vertex connectivity in directed graphs. Inf. Comput, 261 : 248-264.

Georgiadis L.,Italiano G. F.,Karanasiou A.,Parotsidis N.,Paudel N. .2018 .Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: An experimental study. Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), : 169-183.

Henzinger M.,Krinninger S.,Loitzenbauer V.,Iwama K.,Kobayashi N.,Programming B. .2015 .-edge and 2-vertex strongly connected components in quadratic time. ICALP 2015, Lecture Notes in Computer Science, 9134 : 713-724.

Italiano G. F.,Laura L.,Santaroni F. .2012 .Finding strong bridges and strong articulation points in linear time. Theoret. Comput. Sci, 447 : 74-84.

Jaberi R. .2016 .On computing the 2-vertex-connected components of directed graphs. Discrete Appl. Math, 204 : 164-172.

Jaberi R. .2014 .On computing the 2-vertex-connected components of directed graphs. , : 1401.

Jaberi R. .2015 .Computing the 2-blocks of directed graphs. RAIRO-Theor. Inf. Appl, 49 : 93-119.

Jaberi R. .1912 .11799 [cs. , : .

Luigi W. D.,Georgiadis L.,Italiano G. F.,Laura L.,Parotsidis N. .2015 .-Connectivity in directed graphs: An experimental study. Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), : 173-187.

Lengauer T.,Tarjan R. E. .1979 .A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst, 1 : 121-141.

Raghavan S.,Alt B.,Fu M. C.,B. L. M. C. .2006 .Twinless strongly connected components. , 36 : 285-304.

Rose D. J.,Tarjan R. E. .1975 .Algorithmic aspects of vertex elimination. Proceedings of the Seventh Annual ACM Symposium on Theory of Computing (STOC 75), : 245-254.

Schmidt J. .2013 .A simple test on 2-vertex- and 2-edge-connectivity, Inform. , 113 : 241-244.

Tarjan R. E. .1972 .Depth-first search and linear graph algorithms. SIAM J. Comput. 1, : 146-160.