An O(nm) time algorithm for finding the min length directed cycle in a graph

DOI10.1137/1.9781611974782.122MaRDI QIDQ4575868zbMATH OpenOpenAlexFDO

Authors James B. Orlin, Antonio Sedeño-Noda

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.122

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Paths and cycles (05C38)

Recommendations

• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• Automata, Languages and Programming
• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• Algorithms to compute minimum cycle basis in directed graphs
• STACS 2005

Cited in

(12)

• scientific article; zbMATH DE number 3958733 (Why is no real title available?)
• An experimental study of minimum mean cycle algorithms
• The cost-to-time ratio problem for large or infinite graphs
• Directed shortest paths via approximate cost balancing
• scientific article; zbMATH DE number 7204576 (Why is no real title available?)
• Automata, Languages and Programming
• New bounds for the number of lightest cycles in undirected graphs
• A fast algorithm for source-wise round-trip spanners
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Finding minimum cost to time ratio cycles with small integral transit times
• On the power of tree-depth for fully polynomial FPT algorithms
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory

This page was built for publication: An \(O(nm)\) time algorithm for finding the min length directed cycle in a graph

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