English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the $2$-reachability problem we are given a directed graph $G$ and we wishto determine if there are two (edge or vertex) disjoint paths from $u$ to $v$,for a given pair of vertices $u$ and $v$. In this paper, we present analgorithm that computes $2$-reachability information for all pairs of verticesin $\mathcal{O}(n^{\omega}\log n)$ time, where $n$ is the number of verticesand $\omega$ is the matrix multiplication exponent. Hence, we show that therunning time of all-pairs $2$-reachability is only within a $\log$ factor oftransitive closure.  Moreover, our algorithm produces a witness (i.e., a separating edge or aseparating vertex) for all pair of vertices where $2$-reachability does nothold. By processing these witnesses, we can compute all the edge- andvertex-dominator trees of $G$ in $\mathcal{O}(n^2)$ additional time, which inturn enables us to answer various connectivity queries in $\mathcal{O}(1)$time. For instance, we can test in constant time if there is a path from $u$ to$v$ avoiding an edge $e$, for any pair of query vertices $u$ and $v$, and anyquery edge $e$, or if there is a path from $u$ to $v$ avoiding a vertex $w$,for any query vertices $u$, $v$, and $w$.

All-Pairs 2-Reachability in $\mathcal{O}(n^{\omega}\log n)$ Time