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

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

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

(18)

• A shortest cycle for each vertex of a graph
• Approximating the minimum cycle mean
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• Estimating the Length of Material Wrapped Around a Cylindrical Core
• Tight hardness for shortest cycles and paths in sparse graphs
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Approximating the minimum cycle mean
• Faster approximation algorithms for computing shortest cycles on weighted graphs
• Approximating the girth
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems
• Fast distributed algorithms for girth, cycles and small subgraphs
• Computing minimum weight cycle in the CONGEST model
• New bounds for the number of lightest cycles in undirected graphs
• Efficient approximation algorithms for shortest cycles in undirected 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)