Constant girth approximation for directed graphs in subquadratic time

DOI10.1145/3357713.3384330MaRDI QIDQ5144985zbMATH OpenOpenAlexFDO

Authors

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

girthgraphsspanners

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(6)

• A fast algorithm for source-wise round-trip spanners
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Improved sourcewise roundtrip spanners with constant stretch
• Fully dynamic algorithms for minimum weight cycle and related problems
• Near-optimal directed low-diameter decompositions

This page was built for publication: Constant girth approximation for directed graphs in subquadratic time

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