The Kth TSP is pseudopolynomial when TSP is polynomial
From MaRDI portal
Publication:4554540
DOI10.1142/S1793830918500581zbMath1402.90138OpenAlexW2810038234WikidataQ129649471 ScholiaQ129649471MaRDI QIDQ4554540
Publication date: 14 November 2018
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s1793830918500581
traveling salesman problem\(K\) best solutionspseudopolynomial\(K\)th best traveling salesman problem
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding the K best cuts in a network
- On the \(K\)th best base of a matroid
- Solutions of the kth best route through a network. A review
- Ranking arborescences in O(Km log n) time
- Adjacency of the best and second best valued solutions in combinatorial optimization problems
- Thek best spanning arborescences of a network
- An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
- An Algorithm for Finding K Minimum Spanning Trees
- Two Algorithms for Generating Weighted Spanning Trees in Order
- An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Solving the Fixed Charge Problem by Ranking the Extreme Points
- Generalized dynamic programming methods in integer programming
This page was built for publication: The Kth TSP is pseudopolynomial when TSP is polynomial