On the complexity of algorithms for detecting \(k\)-length negative cost cycles
type: Item
instance of: scholarly article
title: On the complexity of algorithms for detecting \(k\)-length negative cost cycles
zbMATH Open document ID: 1480.90211
author: Longkun Guo
author: Peng Li
published in: Journal of Combinatorial Optimization
publication date: 2021-11-25T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7433394
zbMATH Keywords: \(k\)-length negative cost cycle
zbMATH Keywords: \(\mathcal{NP}\)-complete
zbMATH Keywords: 3 occurrence 3-satisfiability
zbMATH Keywords: 3-satisfiability
zbMATH Keywords: randomized algorithm
MaRDI profile type: Publication
full work available at URL: s10878-018-00371-0
OpenAlex ID: W2907639921
cites work: On a routing problem
cites work: Parameterized Algorithms
cites work: Dealing with several parameterized problems by random methods
cites work: Representative Sets of Product Families
cites work: Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
cites work: The directed subgraph homeomorphism problem
cites work: Finding a long directed cycle
cites work: Q4198056
cites work: Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
cites work: On finding Min-Min disjoint paths
cites work: Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints
cites work: Q4635997
cites work: Representative Families: A Unified Tradeoff-Based Approach
cites work: A simplified NP-complete satisfiability problem
DOI: 10.1007/S10878-018-00371-0
Recommended article: On the complexity of detecting \(k\)-length negative cost cycles
Recommended article: Fast algorithms for the undirected negative cost cycle detection problem
Recommended article: Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
Recommended article: Q5740949
Recommended article: Empirical analysis of algorithms for the shortest negative cost cycle problem
Recommended article: Randomized algorithms for finding the shortest negative cost cycle in networks
Recommended article: A zero-space algorithm for negative cost cycle detection in networks
Recommended article: Computational Science – ICCS 2005
Recommended article: On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
Recommended article: On the shortest path problem with negative cost cycles
description: scientific article; zbMATH DE number 7433394