Improved Girth Approximation in Weighted Undirected Graphs
SIAM Journal on Computing · 31.08.2026 · 55 (4) · 560-577
DOI: 10.1137/25m1780286 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.07.2026. Verfasst von Avi Kadria und 4 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: PayPal, Alfred P. Sloan Foundation, Google.
Abstract (Originalsprache)
Let [Formula: see text] be an [Formula: see text]-node [Formula: see text]-edge weighted undirected graph, where [Formula: see text] is a real length function defined on its edges, and let [Formula: see text] denote the girth of [Formula: see text], i.e., the length of a shortest cycle. We present an algorithm that, for any input, integer [Formula: see text], in [Formula: see text] expected time finds a cycle of length at most [Formula: see text]. This algorithm nearly matches an [Formula: see text]-time algorithm of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492] which applied to unweighted graphs of girth 3. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in [Formula: see text] time, where [Formula: see text] is an integral length function, finds a cycle of length at most [Formula: see text] of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492]. For [Formula: see text], this result improves upon the result of Roditty and Tov [ ACM Trans. Algorithms, 9 (2013), pp. 15:1–15:13].
Förderung
- PayPal
- Alfred P. Sloan Foundation
- Microsoft Research
- National Science Foundation
- United States - Israel Binational Science Foundation
Zitieren
APA
Kadria, A., Roditty, L., Sidford, A., Williams, V. V., & Zwick, U. (2026). Improved Girth Approximation in Weighted Undirected Graphs. SIAM Journal on Computing, 55(4), 560-577. https://doi.org/10.1137/25m1780286
Vancouver
Kadria A, Roditty L, Sidford A, Williams VV, Zwick U. Improved Girth Approximation in Weighted Undirected Graphs. SIAM Journal on Computing. 2026;55(4):560-577. doi:10.1137/25m1780286
BibTeX
@article{Kadria2026,
author = {Kadria, Avi and Roditty, Liam and Sidford, Aaron and Williams, Virginia Vassilevska and Zwick, Uri},
title = {Improved Girth Approximation in Weighted Undirected Graphs},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {4},
pages = {560--577},
doi = {10.1137/25m1780286}
}
EUVIMED