Identifying negative cost cycles in strongly polynomial space

MaRDI QIDQ5740949zbMATH OpenFDO

Authors Natarajan Shankar, Pavlos Eirinakis, K. Subramani

Publication date 20 July 2016

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)

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

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)