Approximating the Girth

DOI10.1145/2438645.2438647zbMath1301.05340OpenAlexW2156306627MaRDI QIDQ2933645

Liam Roditty, Roei Tov

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2438645.2438647

zbMATH Keywords

approximationgirthminimum weight cycleweighted undirected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (5)

A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

This page was built for publication: Approximating the Girth