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

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, The complexity of mean payoff games on graphs, Recent development in rigorous computational methods in dynamical systems, An additive eigenvalue problem of physics related to linear programming, The cost-to-time ratio problem for large or infinite graphs, A strongly polynomial algorithm for the minimum cost tension problem, An average polynomial algorithm for solving antagonistic games on graphs, Workload correlations in multi-processor hard real-time systems, A strongly polynomial contraction-expansion algorithm for network flow problems, The use of a synchronizer yields the maximum computation rate in distributed networks, Fully polynomial-time computation of maximum likelihood trajectories in Markov chains, Powers of matrices over an extremal algebra with applications to periodic graphs, Numerical procedure for solving a minimization eigenvalue problem, On matrix powers in max-algebra, On canonical forms for zero-sum stochastic mean payoff games, Maximum cycle-means of weighted digraphs, On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns, A doubly cyclic channel assignment problem, Fractional 0-1 programming: applications and algorithms, The scheduling of maintenance service, A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times, The weak robustness of interval matrices in max-plus algebra, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Algorithms for solving discrete optimal control problems with infinite time horizon and determining minimal mean cost cycles in a directed graph as decision support tool, Randomized algorithms for finding the shortest negative cost cycle in networks, Parametric shortest path algorithms with an application to cyclic staffing, An algorithm for scaling matrices and computing the minimum cycle mean in a digraph, Automated competitive analysis of real-time scheduling with graph games, Complexity results for weighted timed event graphs, Identical coupled task scheduling: polynomial complexity of the cyclic case, On integer images of max-plus linear mappings, On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles., Periodicity of identifying codes in strips, Synthesis of opaque systems with static and dynamic masks, Weighted min cost flows, On short paths interdiction problems: Total and node-wise limited interdiction, Generating constrained length personalized bicycle tours, Minimax algebra and applications, A minimum mean cycle cancelling method for nonlinear multicommodity flow problems, A note on tropical linear and integer programs, Cycle time of a P-time event graph with affine-interdependent residence durations, Linear matrix period in max-plus algebra, Maximizing the spectral radius of a matrix product, Polynomial-time algorithms for energy games with special weight structures, An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix, A special case the of dynamization problem for least cost paths, Heterogeneous string stability of unidirectionally interconnected MIMO LTI systems, Computing periodic request functions to speed-up the analysis of non-cyclic task models, About the minimum mean cycle-canceling algorithm, Synchronization of a class of cyclic discrete-event systems describing legged locomotion, Minimal sensor activation and minimal communication in discrete-event systems, New scaling algorithms for the assignment and minimum mean cycle problems, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, Estimates of the periodic points for nonexpansive operators, A polynomial algorithm for solving system of inequalities in max-plus algebra, Scheduling of coupled tasks and one-machine no-wait robotic cells, Exploring the complexity of the integer image problem in the \(\max\)-algebra, A generalized approximation framework for fractional network flow and packing problems, Computing the throughput of concatenation state machines, Identical part production in cyclic robotic cells: Concepts, overview and open questions, On paths with the shortest average arc length in weighted graphs, Cyclical games with prohibitions, Approximation schemes for stochastic mean payoff games with perfect information and few random positions, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip, The directed orienteering problem, Resource-sharing system scheduling and circular chromatic number, On the performance evaluation of multi-guarded marked graphs with single-server semantics, Minimum degree and density of binary sequences, Online regret bounds for Markov decision processes with deterministic transitions, Mean-payoff games and propositional proofs, Measuring the performance of asynchronous systems with PAFAS, Goldbach's conjecture in max-algebra, On the integer max-linear programming problem, Cycle-based facets of chromatic scheduling polytopes, Minimum mean cycle problem in bidirected and skew-symmetric graphs, An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra., An approximation algorithm for computing longest paths., On the boolean minimal realization problem in the max-plus algebra, Structure and dimension of the eigenspace of a concave Monge matrix, Periodic scheduling with obligatory vacations, On visualization scaling, subeigenvectors and Kleene stars in max algebra, The dynamic predicate stashing copy problem and the Steiner problem in graphs, Simple image set of (max,+) linear mappings, Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones, Applications of shortest path algorithms to matrix scalings, Strong regularity of matrices -- a survey of results, The basic cyclic scheduling problem with deadlines, Finding all the negative cycles in a directed graph, Tight bounds on the number of minimum-mean cycle cancellations and related results, A new saling algorithm for the maximum mean cut problem, Approximate binary search algorithms for mean cuts and cycles, Quantitative characterization of event streams in analysis of hard real-time applications, Upper and lower bounds for stochastic marked graphs, 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

Cites Work