On the complexity of algorithms for detecting k-length negative cost cycles

DOI10.1007/S10878-018-00371-0MaRDI QIDQ2051903zbMATH OpenOpenAlexFDO

Authors Longkun Guo, Peng Li

Publication date 25 November 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-018-00371-0

zbMATH Keywords

3 occurrence 3-satisfiability3-satisfiability\(\mathcal{NP}\)-complete\(k\)-length negative cost cyclerandomized algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• On the complexity of detecting \(k\)-length negative cost cycles
• Fast algorithms for the undirected negative cost cycle detection problem
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Identifying negative cost cycles in strongly polynomial space
• Empirical analysis of algorithms for the shortest negative cost cycle problem
• Randomized algorithms for finding the shortest negative cost cycle in networks
• A zero-space algorithm for negative cost cycle detection in networks
• Computational Science – ICCS 2005
• On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
• On the shortest path problem with negative cost cycles

Cites work

• A simplified NP-complete satisfiability problem
• Dealing with several parameterized problems by random methods
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Finding a long directed cycle
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6863612 (Why is no real title available?)
• Improved approximation algorithms for computing k disjoint paths subject to two constraints
• On a routing problem
• On finding Min-Min disjoint paths
• Parameterized algorithms
• Representative families: a unified tradeoff-based approach
• Representative sets of product families
• The directed subgraph homeomorphism problem

Cited in

(2)

• On the complexity of detecting \(k\)-length negative cost cycles
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks

This page was built for publication: On the complexity of algorithms for detecting \(k\)-length negative cost cycles

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