Randomized algorithms for finding the shortest negative cost cycle in networks

DOI10.1016/j.dam.2017.10.011zbMath1377.05181OpenAlexW2772941018MaRDI QIDQ1693163

James B. Orlin, Piotr Wojciechowki, K. Subramani and Vahan Mkrtchyan

Publication date: 11 January 2018

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

Full work available at URL: https://hdl.handle.net/1721.1/125248

zbMATH Keywords

shortest negative cost cycle problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (4)

Empirical analysis of algorithms for the shortest negative cost cycle problem ⋮ On the analysis of optimization problems in arc-dependent networks ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ On approximating optimal weight ``no-certificates in weighted difference constraint systems

Uses Software

• SMT-LIB
• Yices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal length resolution refutations of difference constraint systems
• On the negative cost girth problem in planar networks
• A characterization of the minimum cycle mean in a digraph
• Application of M-convex submodular flow problem to mathematical economics
• Improved algorithms for optimal length resolution refutation in difference constraint systems
• Computing Small Unsatisfiable Cores in Satisfiability Modulo Theories
• Finding minimum cost to time ratio cycles with small integral transit times
• Parametric dispatching of hard real-time tasks
• Discrete Convex Analysis
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Scaling Algorithms for the Shortest Paths Problem
• Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems
• Fast and Flexible Difference Constraint Propagation for DPLL(T)

This page was built for publication: Randomized algorithms for finding the shortest negative cost cycle in networks