Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm
From MaRDI portal
Publication:846471
DOI10.1016/j.amc.2009.10.053zbMath1189.90182OpenAlexW1971280916MaRDI QIDQ846471
C. Tauras, K. Subramani and Vahan Mkrtchyan, 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
difference constraint systemcontraction-based approachnegative-cycle detectionrelaxation-based approachstressing approach
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Temporal constraint networks
- Shortest paths algorithms: Theory and experimental evaluation
- An analysis of totally clairvoyant scheduling
- A zero-space algorithm for negative cost cycle detection in networks
- On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
- Shortest‐path methods: Complexity, interrelations and new propositions
- A Unified Approach to Path Problems
- Fast Algorithms for Solving Path Problems
- Regular Algebra Applied to Path-finding Problems
- Dual algorithms for the shortest path tree problem
- Negative-cycle detection algorithms
- Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
- Deciding Separation Logic Formulae by SAT and Incremental Negative Cycle Elimination
- The Constraint Database Approach to Software Verification
- An Algebra for Network Routing Problems