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/

Zendy Plus

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

Zendy Tools

Zendy Open

In this paper we study the problem of maintaining the strongly connectedcomponents of a graph in the presence of failures. In particular, we show thatgiven a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value$k\geq 1$, there is an algorithm that computes in $O(2^{k}n\log^2 n)$ time forany set $F$ of size at most $k$ the strongly connected components of the graph$G\setminus F$. The running time of our algorithm is almost optimal since thetime for outputting the SCCs of $G\setminus F$ is at least $\Omega(n)$. Thealgorithm uses a data structure that is computed in a preprocessing phase inpolynomial time and is of size $O(2^{k} n^2)$.  Our result is obtained using a new observation on the relation betweenstrongly connected components (SCCs) and reachability. More specifically, oneof the main building blocks in our result is a restricted variant of theproblem in which we only compute strongly connected components that intersect acertain path. Restricting our attention to a path allows us to implicitlycompute reachability between the path vertices and the rest of the graph intime that depends logarithmically rather than linearly in the size of the path.This new observation alone, however, is not enough, since we need to find anefficient way to represent the strongly connected components using paths. Forthis purpose we use a mixture of old and classical techniques such as the heavypath decomposition of Sleator and Tarjan and the classical Depth-First-Searchalgorithm. Although, these are by now standard techniques, we are not aware ofany usage of them in the context of dynamic maintenance of SCCs. Therefore, weexpect that our new insights and mixture of new and old techniques will be ofindependent interest.

An efficient strongly connected components algorithm in the fault tolerant model