Approximating the minimum cycle mean
From MaRDI portal
Publication:2253203
DOI10.1016/j.tcs.2014.06.031zbMath1417.68284arXiv1307.4473OpenAlexW2048881187MaRDI QIDQ2253203
Krishnendu Chatterjee, Sebastian Krinninger, Michael Raskin, Veronika Loitzenbauer, Monika R. Henzinger
Publication date: 25 July 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.4473
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items (3)
Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Looking at mean-payoff and total-payoff through windows
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time randomizing algorithm for searching ranked functions
- Parametric shortest path algorithms with an application to cyclic staffing
- Positional strategies for mean payoff games
- An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
- New scaling algorithms for the assignment and minimum mean cycle problems
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- A characterization of the minimum cycle mean in a digraph
- Negative-cycle detection algorithms
- Approximate binary search algorithms for mean cuts and cycles
- The complexity of mean payoff games on graphs
- On the exponent of all pairs shortest path problem
- Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles
- Finding minimum cost to time ratio cycles with small integral transit times
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Describing Average- and Longtime-Behavior by Weighted MSO Logics
- New Bounds on the Complexity of the Shortest Path Problem
- Scaling Algorithms for the Shortest Paths Problem
- Faster all-pairs shortest paths via circuit complexity
- Multiplying matrices faster than coppersmith-winograd
- Algorithms – ESA 2005
- Algorithms – ESA 2005
- Faster parametric shortest path and minimum‐balance algorithms
This page was built for publication: Approximating the minimum cycle mean
