The Kth TSP is pseudopolynomial when TSP is polynomial
DOI10.1142/S1793830918500581zbMATH Open1402.90138OpenAlexW2810038234WikidataQ129649471 ScholiaQ129649471MaRDI QIDQ4554540FDOQ4554540
Authors: Brahim Chaourar 
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
Recommendations
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
- Title not available (Why is that?)
- Graph theory
- Introduction to algorithms.
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- 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
- Title not available (Why is that?)
- Solving the Fixed Charge Problem by Ranking the Extreme Points
- An algorithm for determining the \(k\)-best solutions of the one-dimensional knapsack problem
- On the \(K\)th best base of a matroid
- Generalized dynamic programming methods in integer programming
- Title not available (Why is that?)
- On finding the K best cuts in a network
- An \(O(Kn \log (Kn))\) algorithm for the \(K\)th best spanning tree in series parallel graphs
- Thek best spanning arborescences of a network
- 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
This page was built for publication: The \(K\)th TSP is pseudopolynomial when TSP is polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554540)
