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

In this paper, we make use of the Metropolis-type walks due to Nonaka et al.(2010) to provide a faster solution to the $S$-$T$-connectivity problem inundirected graphs (USTCON). As our main result, we propose a family ofrandomized algorithms for USTCON which achieves a time-space product of $S\cdotT = \tilde O(n^2)$ in graphs with $n$ nodes and $m$ edges (where the $\tildeO$-notation disregards poly-logarithmic terms). This improves the previouslybest trade-off of $\tilde O(n m)$, due to Feige (1995). Our algorithm consistsin deploying several short Metropolis-type walks, starting from landmark nodesdistributed using the scheme of Broder et al. (1994) on a modified input graph.In particular, we obtain an algorithm running in time $\tilde O(n+m)$ which is,in general, more space-efficient than both BFS and DFS. We close the paper byshowing how to fine-tune the Metropolis-type walk so as to match theperformance parameters (e.g., average hitting time) of the unbiased random walkfor any graph, while preserving a worst-case bound of $\tilde O(n^2)$ on covertime.

Faster Walks in Graphs: A $\tilde O(n^2)$ Time-Space Trade-off for Undirected s-t Connectivity