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

We consider space efficient implementations of some classical applications ofDFS including the problem of testing biconnectivity and $2$-edge connectivity,finding cut vertices and cut edges, computing chain decomposition and$st$-numbering of a given undirected graph $G$ on $n$ vertices and $m$ edges.Classical algorithms for them typically use DFS and some $\Omega (\lg n)$bits\footnote{We use $\lg$ to denote logarithm to the base $2$.} of informationat each vertex. Building on a recent $O(n)$-bits implementation of DFS due toElmasry et al. (STACS 2015) we provide $O(n)$-bit implementations for all theseapplications of DFS. Our algorithms take $O(m \lg^c n \lg\lg n)$ time for somesmall constant $c$ (where $c \leq 2$). Central to our implementation is asuccinct representation of the DFS tree and a space efficient partitioning ofthe DFS tree into connected subtrees, which maybe of independent interest fordesigning other space efficient graph algorithms.

Biconnectivity, $st$-numbering and other applications of DFS using $O(n)$ bits