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

Let $G$ be a directed graph with $n$ vertices and $m$ edges, and let $s \inV(G)$ be a designated source vertex. We consider the problem of single sourcereachability (SSR) from $s$ in presence of failures of edges (or vertices).Formally, a spanning subgraph $H$ of $G$ is a {\em $k$-Fault TolerantReachability Subgraph ($k$-FTRS)} if it has the following property. For any set$F$ of at most $k$ edges (or vertices) in $G$, and for any vertex $v\in V(G)$,the vertex $v$ is reachable from $s$ in $G-F$ if and only if it is reachablefrom $s$ in $H - F$. Baswana et.al. [STOC 2016, SICOMP 2018] showed that in thesetting above, for any positive integer $k$, we can compute a $k$-FTRS with$2^k n$ edges. In this paper, we give a much simpler algorithm for computing a$k$-FTRS, and observe that it extends to higher connectivity as well. Ourresults follow from a simple application of \emph{important separators}, a wellknown technique in Parameterized Complexity.

A Brief Note on Single Source Fault Tolerant Reachability