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

We consider the problem of approximating the girth, $g$, of an unweighted andundirected graph $G=(V,E)$ with $n$ nodes and $m$ edges. A seminal result ofItai and Rodeh [SICOMP'78] gave an additive $1$-approximation in $O(n^2)$ time,and the main open question is thus how well we can do in subquadratic time.  In this paper we present two main results. The first is a$(1+\varepsilon,O(1))$-approximation in truly subquadratic time. Specifically,for any $k\ge 2$ our algorithm returns a cycle of length $2\lceilg/2\rceil+2\left\lceil\frac{g}{2(k-1)}\right\rceil$ in $\tilde{O}(n^{2-1/k})$time. This generalizes the results of Lingas and Lundell [IPL'09] who showed itfor the special case of $k=2$ and Roditty and Vassilevska Williams [SODA'12]who showed it for $k=3$. Our second result is to present an$O(1)$-approximation running in $O(n^{1+\varepsilon})$ time for any$\varepsilon > 0$. Prior to this work the fastest constant-factor approximationwas the $\tilde{O}(n^{3/2})$ time $8/3$-approximation of Lingas and Lundell[IPL'09] using the algorithm corresponding to the special case $k=2$ of ourfirst result.

New Subquadratic Approximation Algorithms for the Girth