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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we investigate some basic connectivity problems in directedgraphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, andlet $G\setminus e$ be the digraph obtained after deleting edge $e$ from $G$. Asa first result, we show how to compute in $O(m+n)$ worst-case time: $(i)$ Thetotal number of strongly connected components in $G\setminus e$, for all edges$e$ in $G$. $(ii)$ The size of the largest and of the smallest stronglyconnected components in $G\setminus e$, for all edges $e$ in $G$.  Let $G$ be strongly connected. We say that edge $e$ separates two vertices$x$ and $y$, if $x$ and $y$ are no longer strongly connected in $G\setminus e$.As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-spacedata structures that can answer in optimal time the following basicconnectivity queries on digraphs: $(i)$ Report in $O(n)$ worst-case time allthe strongly connected components of $G\setminus e$, for a query edge $e$.$(ii)$ Test whether an edge separates two query vertices in $O(1)$ worst-casetime. $(iii)$ Report all edges that separate two query vertices in optimalworst-case time, i.e., in time $O(k)$, where $k$ is the number of separatingedges. (For $k=0$, the time is $O(1)$).  All of the above results extend to vertex failures. All our bounds are tightand are obtained with a common algorithmic framework, based on a novel compactrepresentation of the decompositions induced by the $1$-connectivity (i.e.,$1$-edge and $1$-vertex) cuts in digraphs, which might be of independentinterest. With the help of our data structures we can design efficientalgorithms for several other connectivity problems on digraphs and we can alsoobtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$edges that maintains the $1$-connectivity cuts of $G$ and the decompositionsinduced by those cuts.

Strong Connectivity in Directed Graphs under Failures, with Application