Edge Elimination in TSP Instances

DOI10.1007/978-3-319-12340-0_23zbMath1417.90128arXiv1402.7301OpenAlexW1855607842MaRDI QIDQ2945197

Stefan Hougardy, Rasmus T. Schroeder

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.7301

zbMATH Keywords

traveling salesman problemexact algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Eulerian and Hamiltonian graphs (05C45)

Related Items (9)

Edge Elimination in TSP Instances ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals ⋮ Special Frequency Quadrilaterals and an Application ⋮ Generalization of machine learning for problem reduction: a case study on travelling salesman problems ⋮ The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals ⋮ Learning to sparsify travelling salesman problem instances

Cites Work

• Unnamed Item
• Unnamed Item
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• Edge Elimination in TSP Instances
• A Dynamic Programming Approach to Sequencing Problems
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: Edge Elimination in TSP Instances