A zero-space algorithm for negative cost cycle detection in networks

DOI10.1016/j.jda.2006.12.002zbMath1149.90314OpenAlexW2007047961MaRDI QIDQ2466006

K. Subramani and Vahan Mkrtchyan

Publication date: 11 January 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.12.002

zbMATH Keywords

polyhedrashortest pathsnegative cost cyclesdifference constraintsrelaxingstressingzero-space

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Related Items (7)

Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm ⋮ MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles ⋮ A combinatorial algorithm for Horn programs ⋮ A mechanical verification of the stressing algorithm for negative cost cycle detection in networks ⋮ Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles ⋮ On the shortest path problem with negative cost cycles ⋮ Fast algorithms for the undirected negative cost cycle detection problem

Cites Work

• Temporal constraint networks
• Scheduling real-time computations with separation constraints
• A theory of timed automata
• Shortest paths algorithms: Theory and experimental evaluation
• Scaling Algorithms for the Shortest Paths Problem
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A zero-space algorithm for negative cost cycle detection in networks