Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

DOI10.1137/20M1330415zbMath1465.05176arXiv1810.10229OpenAlexW2964036608MaRDI QIDQ4990395

Guillaume Ducoffe

Publication date: 28 May 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.10229

zbMATH Keywords

weighted graphsgirthapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (1)

Methods for determining cycles of a specific length in undirected graphs with edge weights

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Approximating the Girth
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• Approximate distance oracles
• Finding a Minimum Circuit in a Graph
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding Even Cycles Even Faster
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Constant girth approximation for directed graphs in subquadratic time
• Approximate distance oracles with constant query time
• Better Approximation Algorithms for the Graph Diameter
• Distance Oracles beyond the Thorup--Zwick Bound
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• On Graphs that do not Contain a Thomsen Graph
• Automata, Languages and Programming

This page was built for publication: Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs