scientific article; zbMATH DE number 7204576

DOI10.4230/LIPICS.ICALP.2017.124MaRDI QIDQ5111456zbMATH OpenFDO

Authors Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger

Publication date 27 May 2020

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

zbMATH Keywords

shortest pathsparametric searchnegative cycle detectionquantitative verification and synthesis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)

Recommendations

• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• An \(O(nm)\) time algorithm for finding the min length directed cycle in a graph
• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• Algorithms to compute minimum cycle basis in directed graphs
• STACS 2005
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• A greedy approach to compute a minimum cycle basis of a directed graph
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Algorithms for finding the minimum cycle mean in the weighted directed graph

Cited in

(4)

• Finding minimum cost to time ratio cycles with small integral transit times
• Shortest distances as enumeration problem
• Faster algorithms for quantitative verification in constant treewidth graphs
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory

This page was built for publication:

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