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

(I) We revisit the algorithmic problem of finding all triangles in a graph$G=(V,E)$ with $n$ vertices and $m$ edges. According to a result of Chiba andNishizeki (1985), this task can be achieved by a combinatorial algorithmrunning in $O(m \alpha) = O(m^{3/2})$ time, where $\alpha= \alpha(G)$ is thegraph arboricity. We provide a new very simple combinatorial algorithm forfinding all triangles in a graph and show that is amenable to the same runningtime analysis. We derive these worst-case bounds from first principles and withvery simple proofs that do not rely on classic results due to Nash-Williamsfrom the 1960s.  (II) We extend our arguments to the problem of finding all small completesubgraphs of a given fixed size. We show that the dependency on $m$ and$\alpha$ in the running time $O(\alpha^{\ell-2} \cdot m)$ of the algorithm ofChiba and Nishizeki for listing all copies of $K_\ell$, where $\ell \geq 3$, isasymptotically tight.  (III) We give improved arboricity-sensitive running times for counting and/ordetection of copies of $K_\ell$, for small $\ell \geq 4$. A key ingredient inour algorithms is, once again, the algorithm of Chiba and Nishizeki. Our newalgorithms are faster than all previous algorithms in certain high-rangearboricity intervals for every $\ell \geq 7$.

Finding Small Complete Subgraphs Efficiently