The Kth TSP is pseudopolynomial when TSP is polynomial

DOI10.1142/S1793830918500581zbMath1402.90138OpenAlexW2810038234WikidataQ129649471 ScholiaQ129649471MaRDI QIDQ4554540

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

zbMATH Keywords

traveling salesman problem\(K\) best solutionspseudopolynomial\(K\)th best traveling salesman problem

Mathematics Subject Classification ID

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