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

DOI10.1016/J.JDA.2006.12.002MaRDI QIDQ2466006zbMATH OpenOpenAlexFDO

Authors K. Subramani

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

difference constraintsnegative cost cyclespolyhedrarelaxingshortest pathsstressingzero-space

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Recommendations

• Identifying negative cost cycles in strongly polynomial space
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks
• Negative-cycle detection algorithms
• Negative-cycle detection algorithms

Cites work

• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• A theory of timed automata
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 4083375 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080043 (Why is no real title available?)
• scientific article; zbMATH DE number 2081016 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Scaling Algorithms for the Shortest Paths Problem
• Scheduling real-time computations with separation constraints
• Shortest paths algorithms: Theory and experimental evaluation
• Temporal constraint networks

Cited in

(13)

• Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
• A combinatorial algorithm for Horn programs
• On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
• Fast algorithms for the undirected negative cost cycle detection problem
• Negative-cycle detection algorithms
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks
• Computational Science – ICCS 2005
• Identifying negative cost cycles in strongly polynomial space
• On the shortest path problem with negative cost cycles
• Projection methods for finding the greatest element of the intersection of max-closed convex sets
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2466006)