Identifying negative cost cycles in strongly polynomial space

zbMATH Open1364.68313MaRDI QIDQ5740949FDOQ5740949

Authors: Natarajan Shankar, Pavlos Eirinakis, K. Subramani 

Publication date: 20 July 2016

Recommendations

• 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
• Negative-cycle detection algorithms
• Negative-cycle detection algorithms
• Randomized algorithms for finding the shortest negative cost cycle in networks

zbMATH Keywords

negative cycle detectionnegative cycle identificationpointer chasingpredecessor subgraphspace-optimalstressing algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (3)

• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• 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

This page was built for publication: Identifying negative cost cycles in strongly polynomial space

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