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

DOI10.1007/s10878-018-00371-0zbMath1480.90211OpenAlexW2907639921MaRDI QIDQ2051903

Peng Li, Longkun Guo

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

randomized algorithm3-satisfiability\(\mathcal{NP}\)-complete\(k\)-length negative cost cycle3 occurrence 3-satisfiability

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• A simplified NP-complete satisfiability problem
• The directed subgraph homeomorphism problem
• Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
• On finding Min-Min disjoint paths
• Dealing with several parameterized problems by random methods
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• On a routing problem
• Finding a long directed cycle
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Parameterized Algorithms

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