In this paper, we investigate some basic connectivity problems in directed graphs (digraphs).
Let G be a digraph with m edges and n vertices, and let G∖e (resp., G∖v) be the digraph …

Edge and vertex connectivity are fundamental concepts in graph theory. While they have
been thoroughly studied in the case of undirected graphs, surprisingly, not much has been …

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 consider the problem of computing the 2-vertex-connected components of
directed graphs. We present a new algorithm for solving this problem in O (nm) time …

We introduce a new dynamic data structure for maintaining the strongly connected
components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a …

Abstract Let G=(V, E) be a directed graph. A 2-edge-twinless block in G is a maximal vertex
set C t⊆ V with| C t|> 1 such that for any distinct vertices v, w∈ C t, and for every edge e∈ E …

Motivated by very recent work on 2-connectivity in directed graphs, we revisit the problem of
computing the 2-edge-and 2-vertex-connected components, and the maximal 2-edge-and 2 …

Let $ G=(V, E) $ be a twinless strongly connected graph. a vertex $ v\in V $ is a twinless
articulation point if the subrgraph obtained from $ G $ by removing the vertex $ v $ is not …

Let G be a strongly connected directed graph. We consider the following three problems,
where we wish to compute the smallest strongly connected spanning subgraph of G that …

Let $ G=(V, E)) $ be a directed graph. A $2 $-twinless block in $ G $ is a maximal vertex set
$ B\subseteq V $ of size at least $2 $ such that for each pair of distinct vertices $ x, y\in B …