Minimum Weight Cycles and Triangles: Equivalences and Algorithms

DOI10.1109/FOCS.2011.27MaRDI QIDQ5495016zbMATH OpenFDO

Authors Liam Roditty, Virginia Vassilevska Williams

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

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

Cited in

(11)

• Improved distance queries and cycle counting by Frobenius normal form
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• scientific article; zbMATH DE number 7561542 (Why is no real title available?)
• Triangles and girth in disk graphs and transmission graphs
• Fast distributed algorithms for girth, cycles and small subgraphs
• A shortest cycle for each vertex of a graph
• From circuit complexity to faster all-pairs shortest paths
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• Improved time bounds for all pairs non-decreasing paths in general digraphs

This page was built for publication: Minimum Weight Cycles and Triangles: Equivalences and Algorithms

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