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

DOI10.1137/1.9781611974782.122zbMATH Open1410.68304OpenAlexW2907002631MaRDI QIDQ4575868FDOQ4575868

Antonio Sedeño-Noda, James B. Orlin

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

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

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)

Cited In (9)

• Title not available (Why is that?)
• The cost-to-time ratio problem for large or infinite graphs
• Directed shortest paths via approximate cost balancing
• Title not available (Why is that?)
• Automata, Languages and Programming
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• A fast algorithm for source-wise round-trip spanners
• Finding minimum cost to time ratio cycles with small integral transit times
• On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

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)