On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection

DOI10.1016/J.AMC.2005.04.005MaRDI QIDQ2489173zbMATH OpenOpenAlexFDO

Authors D. Desovski, K. Subramani

Publication date 16 May 2006

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2005.04.005

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• Computational Science – ICCS 2005
• Negative-cycle detection algorithms
• Negative-cycle detection algorithms
• A zero-space algorithm for negative cost cycle detection in networks
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm

Cites work

• A heuristic improvement of the Bellman-Ford algorithm
• A Unified Approach to Path Problems
• Algorithm design: Foundations, analysis, and Internet examples
• An Algebra for Network Routing Problems
• Combinatorial optimization. Theory and algorithms
• Dual algorithms for the shortest path tree problem
• Fast Algorithms for Solving Path Problems
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3958733 (Why is no real title available?)
• scientific article; zbMATH DE number 3711960 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 2080043 (Why is no real title available?)
• scientific article; zbMATH DE number 2080869 (Why is no real title available?)
• scientific article; zbMATH DE number 2081016 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• Implementation and efficiency of Moore-algorithms for the shortest route problem
• Negative-cycle detection algorithms
• Network flows. Theory, algorithms, and applications.
• Regular Algebra Applied to Path-finding Problems
• Scaling Algorithms for the Shortest Paths Problem
• Scheduling real-time computations with separation constraints
• Shortest paths algorithms: Theory and experimental evaluation
• Shortest‐path methods: Complexity, interrelations and new propositions
• Temporal constraint networks

Cited in

(4)

• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks
• Computational Science – ICCS 2005
• Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection

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