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

Consider the problem of maintaining source sinkreachability($st$-Reachability), single source reachability(SSR) and stronglyconnected component(SCC) in an edge decremental directed graph. In particular,we design a randomized algorithm that maintains with high probability:  1) $st$-Reachability in $\tilde{O}(mn^{4/5})$ total update time. 2)$st$-Reachability in a total update time of $\tilde{O}(n^{8/3})$ in a densegraph. 3) SSR in a total update time of $\tilde{O}(m n^{9/10})$. 4) SCC in atotal update time of $\tilde{O}(m n^{9/10})$. For all the above problems, weimprove upon the previous best algorithm (by Henzinger et. al. (STOC 2014)).  Our main focus is maintaining $st$-Reachability in an edge decrementaldirected graph (other problems can be reduced to $st$-Reachability). Theclassical algorithm of Even and Shiloach (JACM 81) solved this problem in$O(1)$ query time and $O(mn)$ total update time. Recently, Henzinger,Krinninger and Nanongkai (STOC 2014) designed a randomized algorithm whichachieves an update time of $\tilde{O}(m n^{0.98})$ and broke the long-standing$O(mn)$ bound of Even and Shiloach. However, they designed four algorithms $A_i(1\le i \le 4)$ such that for graphs having total number of edges between $m_i$and $m_{i+1}$ ($m_{i+1} > m_i$), $A_i$ outperforms other three algorithms. Thatis, one of the four algorithms may be faster for a particular density range ofedges, but it may be too slow asymptotically for the other ranges. Our maincontribution is that we design a {\it single} algorithm which works for alltypes of graphs. Not only is our algorithm faster, it is much simpler than thealgorithm designed by Henzinger et.al. (STOC 2014).

Simple and Faster algorithm for Reachability in a Decremental Directed Graph