Minimum 2-vertex strongly biconnected spanning directed subgraph problem

Raed Jaberi

doi:10.47443/dml.2021.0024

Author(s)

Raed Jaberi Department of Software and Information Systems, Tishreen University, Latakia, Syrian Arab Republic

Abstract

A directed graph G = (V; E) is strongly biconnected if G is strongly connected and its underlying graph is biconnected. A strongly biconnected directed graph G = (V; E) is called 2-vertex-strongly biconnected if jV j 3 and the induced subgraph on V n fwg is strongly biconnected for every vertex w 2 V . In this paper, the following problem is studied: Given a 2-vertexstrongly biconnected directed graph G = (V; E), compute an edge subset E2sb E of minimum size such that the subgraph (V; E2sb) is 2-vertex-strongly biconnected.

Publication Details

Page(s) 40-43

DOI 10.47443/dml.2021.0024

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

Request the full text from PASTIC

Keywords

strongly biconnected directed graphs, strongly connected graphs, directed graphs, approximation algorithms, graph algorithms

References

Cheriyan J.,Thurimella R. .2000 .Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput, 30 : 528-560.

Edmonds J.,Combinatorial Algorithms .1972 .Edge-disjoint branchings. , : 91-96.

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.

Garey M. R.,Johnson D. S.,Completeness W. H.,Freeman W. H. .1979 .Computers and Intractability: A Guide to the Theory of NP-. , : .

Georgiadis L.,Gavoille C.,Kirchner C. .2010 .-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.,Demetrescu L. .2011 .Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. Algorithms - ESA 2011, Lecture Notes in Computer Science, 6942 : 13-24.

Georgiadis L.,Italiano G. F.,Karanasiou A. .2020 .Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. Theoret. Comput. Sci, 807 : 185-200.

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.,Tarjan R. E. .2016 .Dominator tree certification and divergent spanning trees. ACM Trans. Algorithms, 12 : 11.

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. .2019 .11799 [cs. , : .

Jaberi R. . .-edge-twinless blocks. Bull. Sci. Math, 168(2021) : 102969.

Jaberi R. .2021 .. Discrete Math. Lett. 5, : 29-33.

Mader W. .1971 .Minimal n-fach kantenzusammenh a¨ngende graphen. , 191 : 21-28.

Mader W. .1972 .Ecken vom grad n in minimalen n-fach zusammenhängenden graphen. , 23 : 219-224.

Mader W. .1985 .Minimal n-fach zusammenha¨ ngende digraphen. J. Combin. Theory Ser. B, 38 : 102-117.

J. M. Schmidt .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.

Wu Z.,Grumbach S. .2010 .Feasibility of motion planning on acyclic and strongly connected directed graphs. Discrete Appl. Math, 158 : 1017-1028.