Approximating the girth

DOI10.1145/2438645.2438647MaRDI QIDQ2933645zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Approximating the girth
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Approximating the minimum cycle mean

Cited in

(16)

• A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• scientific article; zbMATH DE number 7561542 (Why is no real title available?)
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Approximating the minimum cycle mean
• Approximating the girth
• Estimating the Length of Material Wrapped Around a Cylindrical Core
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• Fast distributed algorithms for girth, cycles and small subgraphs
• A shortest cycle for each vertex of a graph
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Approximating the minimum cycle mean
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Tight hardness for shortest cycles and paths in sparse graphs

This page was built for publication: Approximating the girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933645)