Approximating the girth
From MaRDI portal
Publication:2933645
DOI10.1145/2438645.2438647zbMATH Open1301.05340OpenAlexW2156306627MaRDI QIDQ2933645FDOQ2933645
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
Recommendations
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)
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
- Title not available (Why is that?)
- 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)