Optimal Girth Approximation for Dense Directed Graphs

In this paper we provide a Õ ( n 2 ) time algorithm that computes a 2-multiplicative approximation of the girth of an n -node m -edge directed graph with non-negative edge weights. We also provide an additional algorithm that computes a 2-multiplicative approximation of the girth in time 1. Our results naturally provide algorithms for improved constructions of 4-roundtrip spanners, the analog of spanners in directed graphs. Our algorithm is optimal (up to a log n factor) for dense graphs with m = Θ( n 2 ). For comparison, previously, the best approximation ratio with a similar running time for dense graphs was O (log n log log n ) [1]. Moreover, unlike previous algorithms, our algorithm neither assumes integer weights, nor does it depend on the maximum edge weight of the graph.

Authors

• Shiri Chechik
• Gur Lifshitz

Keywords

No keywords are indexed for this paper.