pipette
ENEnglish

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

Eliyahu Yablon

Preprint

En palabras de los autores

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized algorithm to approximate the girth of a graph with vertices and edges to within a factor of for any real . We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors where , our algorithm gives a runtime of , while instantiating the previous best -approximation algorithms with yields a running time of (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call "random filtering." That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

Resultado principalLimitación que admiten los autores

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.