Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm

DOI10.1016/J.AMC.2009.10.053MaRDI QIDQ846471zbMATH OpenOpenAlexFDO

Authors C. Tauras, K. Subramani, Kamesh Madduri

Publication date 9 February 2010

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

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

zbMATH Keywords

difference constraint systemcontraction-based approachnegative-cycle detectionrelaxation-based approachstressing approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10)

Recommendations

• A zero-space algorithm for negative cost cycle detection in networks
• Identifying negative cost cycles in strongly polynomial space
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks
• Negative-cycle detection algorithms
• Negative-cycle detection algorithms

Cites work

• scientific article; zbMATH DE number 5764826 (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 1979548 (Why is no real title available?)
• A Unified Approach to Path Problems
• A zero-space algorithm for negative cost cycle detection in networks
• An Algebra for Network Routing Problems
• An analysis of totally clairvoyant scheduling
• Deciding Separation Logic Formulae by SAT and Incremental Negative Cycle Elimination
• Dual algorithms for the shortest path tree problem
• Fast Algorithms for Solving Path Problems
• Introduction to algorithms
• Negative-cycle detection algorithms
• Network flows. Theory, algorithms, and applications.
• On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
• Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
• Regular Algebra Applied to Path-finding Problems
• Shortest paths algorithms: Theory and experimental evaluation
• Shortest‐path methods: Complexity, interrelations and new propositions
• Temporal constraint networks
• The Constraint Database Approach to Software Verification

Cited in

(4)

• Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
• On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
• A zero-space algorithm for negative cost cycle detection in networks
• Identifying negative cost cycles in strongly polynomial space

Describes a project that uses

Uses Software

• Netsoft

This page was built for publication: Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm

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