Source author record

Raed Jaberi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

11works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Minimum $2$ -edge strongly biconnected spanning directed subgraph problem

Wu and Grumbach introduced the concept of strongly biconnected directed graphs. A directed graph $G=(V,E)$ is called strongly biconnected if the directed graph $G$ is strongly connected and the underlying undirected graph of $G$ is biconnected. A strongly biconnected directed graph $G=(V,E)$ is said to be $2$ - edge strongly biconnected if it has at least three vertices and the directed subgraph $(V,E\setminus\left\lbrace e\right\rbrace )$ is strongly biconnected for all $e \in E$ . Let $G=(V,E)$ be a $2$ -edge-strongly biconnected directed graph. In this paper we study the problem of computing a minimum size subset $H \subseteq E$ such that the directed subgraph $(V,H)$ is $2$ - edge strongly biconnected.

preprint2022arXiv

Minimum strongly biconnected spanning directed subgraph problem

Let $G=(V,E)$ be a strongly biconnected directed graph. In this paper we consider the problem of computing an edge subset $H \subseteq E$ of minimum size such that the directed subgraph $(V,H)$ is strongly biconnected.

preprint2021arXiv

Computing $2$ -twinless blocks

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$ , and for each vertex $w\in V\setminus\left\lbrace x,y \right\rbrace$ , the vertices $x,y$ are in the same twinless strongly connected component of $G\setminus\left \lbrace w \right\rbrace$ . In this paper we present algorithms for computing the $2$ -twinless blocks of a directed graph.

preprint2020arXiv

$2$ -blocks in strongly biconnected directed graphs

A directed graph $G=(V,E)$ is called strongly biconnected if $G$ is strongly connected and the underlying graph of $G$ is biconnected. A strongly biconnected component of a strongly connected graph $G=(V,E)$ is a maximal vertex subset $L\subseteq V$ such that the induced subgraph on $L$ is strongly biconnected. Let $G=(V,E)$ be a strongly biconnected directed graph. A $2$ -edge-biconnected block in $G$ is a maximal vertex subset $U\subseteq V$ such that for any two distict vertices $v,w \in U$ and for each edge $b\in E$ , the vertices $v,w$ are in the same strongly biconnected components of $G\setminus\left\lbrace b\right\rbrace$ . A $2$ -strong-biconnected block in $G$ is a maximal vertex subset $U\subseteq V$ of size at least $2$ such that for every pair of distinct vertices $v,w\in U$ and for every vertex $z\in V\setminus\left\lbrace v,w \right\rbrace$ , the vertices $v$ and $w$ are in the same strongly biconnected component of $G\setminus \left\lbrace v,w \right\rbrace$ . In this paper we study $2$ -edge-biconnected blocks and $2$ -strong biconnected blocks.

preprint2020arXiv

$2$ -edge-twinless blocks

Let $G=(V,E)$ be a directed graph. A $2$ -edge-twinless block in $G$ is a maximal vertex set $C^{t}\subseteq V$ with $|C^{t}|>1$ such that for any distinct vertices $v,w \in C^{t}$ , and for every edge $e\in E$ , the vertices $v,w$ are in the same twinless strongly connected component of $G\setminus\left \lbrace e \right\rbrace$ . In this paper we study this concept and describe algorithms for computing $2$ -edge-twinless blocks.

preprint2020arXiv

b-articulation points and b-bridges in strongly biconnected directed graphs

A directed graph $G=(V,E)$ is called strongly biconnected if $G$ is strongly connected and the underlying graph of $G$ is biconnected. This class of directed graphs was first introduced by Wu and Grumbach. Let $G=(V,E)$ be a strongly biconnected directed graph. An edge $e\in E$ is a b-bridge if the subgraph $G\setminus \left\lbrace e\right\rbrace =(V,E\setminus \left\lbrace e\right\rbrace)$ is not strongly biconnected. A vertex $w\in V$ is a b-articulation point if $G\setminus \left\lbrace w\right\rbrace$ is not strongly biconnected, where $G\setminus \left\lbrace w\right\rbrace$ is the subgraph obtained from $G$ by removing $w$ . In this paper we study b-articulation points and b-bridges.

preprint2020arXiv

Minimum $2$ -vertex strongly biconnected spanning directed subgraph problem

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 $|V|\geq 3$ and the induced subgraph on $V\setminus\left\lbrace w\right\rbrace$ is strongly biconnected for every vertex $w\in V$ . In this paper we study the following problem. Given a $2$ -vertex-strongly biconnected directed graph $G=(V,E)$ , compute an edge subset $E^{2sb} \subseteq E$ of minimum size such that the subgraph $(V,E^{2sb})$ is $2$ -vertex-strongly biconnected.

preprint2020arXiv

Minimum $2$ -vertex-twinless connected spanning subgraph problem

Given a $2$ -vertex-twinless connected directed graph $G=(V,E)$ , the minimum $2$ -vertex-twinless connected spanning subgraph problem is to find a minimum cardinality edge subset $E^{t} \subseteq E$ such that the subgraph $(V,E^{t})$ is $2$ -vertex-twinless connected. Let $G^{1}$ be a minimal $2$ -vertex-connected subgraph of $G$ . In this paper we present a $(2+a_{t}/2)$ -approximation algorithm for the minimum $2$ -vertex-twinless connected spanning subgraph problem, where $a_{t}$ is the number of twinless articulation points in $G^{1}$ .

preprint2015arXiv

On testing single connectedness in directed graphs and some related problems

Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The graph $G$ is called singly-connected if for each pair of vertices $v,w \in V$ there is at most one simple path from $v$ to $w$ in $G$ . Buchsbaum and Carlisle (1993) gave an algorithm for testing whether $G$ is singly-connected in $O(n^{2})$ time. In this paper we describe a refined version of this algorithm with running time $O(s\cdot t+m)$ , where $s$ and $t$ are the number of sources and sinks, respectively, in the reduced graph $G^{r}$ obtained by first contracting each strongly connected component of $G$ into one vertex and then eliminating vertices of indegree or outdegree $1$ by a contraction operation. Moreover, we show that the problem of finding a minimum cardinality edge subset $C\subseteq E$ (respectively, vertex subset $F\subseteq V$ ) whose removal from $G$ leaves a singly-connected graph is NP-hard.

preprint2014arXiv

Computing the $2$ -blocks of directed graphs

Let $G$ be a directed graph. A \textit{ $2$ -directed block} in $G$ is a maximal vertex set $C^{2d}\subseteq V$ with $|C^{2d}|\geq 2$ such that for each pair of distinct vertices $x,y \in C^{2d}$ , there exist two vertex-disjoint paths from $x$ to $y$ and two vertex-disjoint paths from $y$ to $x$ in $G$ . In contrast to the $2$ -vertex-connected components of $G$ , the subgraphs induced by the $2$ -directed blocks may consist of few or no edges. In this paper we present two algorithms for computing the $2$ -directed blocks of $G$ in $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$ time, where $t_{sap}$ is the number of the strong articulation points of $G$ and $t_{sb}$ is the number of the strong bridges of $G$ . Furthermore, we study two related concepts: the $2$ -strong blocks and the $2$ -edge blocks of $G$ . We give two algorithms for computing the $2$ -strong blocks of $G$ in $O( \min \lbrace m,t_{sap} n\rbrace n)$ time and we show that the $2$ -edge blocks of $G$ can be computed in $O(\min \lbrace m, t_{sb} n \rbrace n)$ time. In this paper we also study some optimization problems related to the strong articulation points and the $2$ -blocks of a directed graph. Given a strongly connected graph $G=(V,E)$ , find a minimum cardinality set $E^{*}\subseteq E$ such that $G^{*}=(V,E^{*})$ is strongly connected and the strong articulation points of $G$ coincide with the strong articulation points of $G^{*}$ . This problem is called minimum strongly connected spanning subgraph with the same strong articulation points. We show that there is a linear time $17/3$ approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same $2$ -blocks in a strongly connected graph $G$ . We present approximation algorithms for three versions of this problem, depending on the type of $2$ -blocks.

preprint2014arXiv

On computing the $2$ -vertex-connected components of directed graphs

In this paper we consider the problem of computing the $2$ -vertex-connected components ( $2$ -vccs) of directed graphs. We present two new algorithms for solving this problem. The first algorithm runs in $O(mn^{2})$ time, the second in $O(nm)$ time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in $O(nm^{2})$ time. In this paper, we investigate the relationship between $2$ -vccs and dominator trees. We also present an algorithm for computing the $3$ -vertex-connected components ( $3$ -vccs) of a directed graph in $O(n^{3}m)$ time, and we show that the $k$ -vertex-connected components ( $k$ -vccs) of a directed graph can be computed in $O(mn^{2k-3})$ time. Finally, we consider three applications of our new algorithms, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest $2$ -vertex-connected spanning subgraph of $2$ -vertex-connected directed graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Raed Jaberi

Research overview

Is this your work?

11 publications

Minimum $2$ -edge strongly biconnected spanning directed subgraph problem

Minimum strongly biconnected spanning directed subgraph problem

Computing $2$ -twinless blocks

$2$ -blocks in strongly biconnected directed graphs

$2$ -edge-twinless blocks

b-articulation points and b-bridges in strongly biconnected directed graphs

Minimum $2$ -vertex strongly biconnected spanning directed subgraph problem

Minimum $2$ -vertex-twinless connected spanning subgraph problem

On testing single connectedness in directed graphs and some related problems

Computing the $2$ -blocks of directed graphs

On computing the $2$ -vertex-connected components of directed graphs

See the researcher in context

Building this map preview

Raed Jaberi

Research overview

Is this your work?

11 publications

Minimum 222-edge strongly biconnected spanning directed subgraph problem

Minimum strongly biconnected spanning directed subgraph problem

Computing 222-twinless blocks

222-blocks in strongly biconnected directed graphs

222-edge-twinless blocks

b-articulation points and b-bridges in strongly biconnected directed graphs

Minimum 222-vertex strongly biconnected spanning directed subgraph problem

Minimum 222-vertex-twinless connected spanning subgraph problem

On testing single connectedness in directed graphs and some related problems

Computing the 222-blocks of directed graphs

On computing the 222-vertex-connected components of directed graphs

See the researcher in context

Building this map preview

Minimum $2$ -edge strongly biconnected spanning directed subgraph problem

Computing $2$ -twinless blocks

$2$ -blocks in strongly biconnected directed graphs

$2$ -edge-twinless blocks

Minimum $2$ -vertex strongly biconnected spanning directed subgraph problem

Minimum $2$ -vertex-twinless connected spanning subgraph problem

Computing the $2$ -blocks of directed graphs

On computing the $2$ -vertex-connected components of directed graphs