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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m-edge and n-node graphs require Ω(min{nω, mn}) time (for 2 ≤ ω > 2.373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in O(m) time computes an O(n)-multiplicative approximation of the girth as well as an O(n)-multiplicative roundtrip spanner with O(n) edges with high probability (w.h.p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∈ (0, 1) we give an algorithm that in O(mn1−a) time computes an 0(na)-additive approximation of the girth, w.h.p. We show that the run-time of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is 0(na), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω(mn) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners