A characterization of the minimum cycle mean in a digraph

DOI10.1016/0012-365X(78)90011-0zbMath0386.05032WikidataQ126778831 ScholiaQ126778831MaRDI QIDQ1249587

Publication date: 1978

Published in: Discrete Mathematics (Search for Journal in Brave)

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (only showing first 100 items - show all)

Hyperplane separation technique for multidimensional mean-payoff games ⋮ On the complexity and approximability of budget-constrained minimum cost flows ⋮ The power algorithm in max algebra ⋮ The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory ⋮ Methods and applications of (max,+) linear algebra ⋮ Combinatorial algorithms for inverse network flow problems ⋮ The Combinatorial World (of Auctions) According to GARP ⋮ Unnamed Item ⋮ On the capabilities of systolic systems ⋮ Understanding retiming through maximum average-delay cycles ⋮ Approximating a class of combinatorial problems with rational objective function ⋮ Optimal Embedding into Star Metrics ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Dynamic analysis of repetitive decision-free discrete-event processes: The algebra of timed marked graphs and algorithmic issues ⋮ Cyclic schedules for r irregularity occurring events ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A note on finding minimum mean cycle ⋮ Solving a constrained economic lot size problem by ranking efficient production policies ⋮ TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix ⋮ \(p\)-dominant switched linear systems ⋮ Analysis and control of max-plus linear discrete-event systems: an introduction ⋮ Mean-payoff games with \(\omega\)-regular specifications ⋮ Average-energy games ⋮ Shortest Paths in Nearly Conservative Digraphs ⋮ Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ Graph planning with expected finite horizon ⋮ Model-Based Verification, Optimization, Synthesis and Performance Evaluation of Real-Time Systems ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ Computing the average inter-sample time of event-triggered control using quantitative automata ⋮ The complexity of mean payoff games ⋮ Efficient Computation of Throughput Values of Context-Free Languages ⋮ Cooperative concurrent games ⋮ Computing the sampling performance of event-triggered control ⋮ ETCetera: beyond Event-Triggered Control ⋮ Graph-Based Dwell Time Computation Methods for Discrete-Time Switched Linear Systems ⋮ Value Iteration ⋮ On the prevalence of the periodicity of maximizing measures ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ Cyclic flowshop scheduling with operators and robots: Vyacheslav Tanaev's vision and lasting contributions ⋮ New algorithms for solving tropical linear systems ⋮ Unnamed Item ⋮ Encodings of trajectories and invariant measures ⋮ Dwell time and average dwell time methods based on the cycle ratio of the switching graph ⋮ On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost ⋮ Avoiding or Limiting Regularities in Words ⋮ The robustness of interval matrices in max-plus algebra ⋮ Online Regret Bounds for Markov Decision Processes with Deterministic Transitions ⋮ Unnamed Item ⋮ Certifying Unstability of Switched Systems Using Sum of Squares Programming ⋮ Throughput Scalability Analysis of Fork-Join Queueing Networks ⋮ Bounding Average-Energy Games ⋮ On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness ⋮ Graph Lyapunov function for switching stabilization and distributed computation ⋮ Computing an eigenvector of a Monge matrix in max-plus algebra ⋮ Optimal infinite scheduling for multi-priced timed automata ⋮ Structure of the eigenspace of a Monge matrix in max-plus algebra ⋮ A survey of computational complexity results in systems and control ⋮ Permuted max-algebraic eigenvector problem is \(NP\)-complete ⋮ Approximating the minimum cycle mean ⋮ A method for approximating symmetrically reciprocal matrices by transitive matrices ⋮ Unnamed Item ⋮ A simplex-like method to compute the eigenvalue of an irreducible \((\max,+)\)-system ⋮ Modifying the power method in max algebra ⋮ Faster parametric shortest path and minimum‐balance algorithms ⋮ The Robot Routing Problem for Collecting Aggregate Stochastic Rewards ⋮ Elasticity and Petri Nets ⋮ Unnamed Item ⋮ A mean-variance model for the minimum cost flow problem with stochastic arc costs ⋮ A polyhedral study of the acyclic coloring problem ⋮ Unnamed Item ⋮ On covering by translates of a set ⋮ Uniform Expansivity Outside a Critical Neighborhood in the Quadratic Family ⋮ Distribution and quantile functions, ranks and signs in dimension \(d\): a measure transportation approach ⋮ Triangulations with Circular Arcs ⋮ Performance Enhancement of Asynchronous Circuits ⋮ Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution ⋮ A note on weighted minimal cost flows ⋮ The Complexity of Nash Equilibria in Limit-Average Games ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Cyclic lot-sizing problems with sequencing costs ⋮ The characterizations of irreducible matrices with proper supereigenvectors ⋮ Taming the knight's tour: minimizing turns and crossings ⋮ Dynamic Observers for the Synthesis of Opaque Systems ⋮ The minimum mean cycle-canceling algorithm for linear programs ⋮ Intertemporal Price Discrimination with Time-Varying Valuations ⋮ Eigenvectors of interval matrices over max--plus algebra ⋮ \(\ell\)-parametric eigenproblem in max-algebra ⋮ The complexity of multi-mean-payoff and multi-energy games ⋮ Looking at mean-payoff and total-payoff through windows ⋮ Finding minimum cost to time ratio cycles with small integral transit times ⋮ A strongly polynomial method for solving integer max-linear optimization problems in a generic case ⋮ Computing optimal scalings by parametric network algorithms ⋮ The maximum ratio clique problem ⋮ On tropical supereigenvectors ⋮ Computing maximum mean cuts ⋮ Optimal precision in the presence of uncertainty ⋮ Min-max functions ⋮ Scheduling for stability in single-machine production systems ⋮ Cache-aware timing analysis of streaming applications ⋮ Extremal eigenproblem for bivalent matrices

Cites Work

This page was built for publication: A characterization of the minimum cycle mean in a digraph