EUVIMEDEUVIMED entdecken
Crossref

Improved Girth Approximation in Weighted Undirected Graphs

Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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
  • Google
  • 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}
}
Kostenlos starten →