A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions

DOI10.1016/j.disopt.2017.08.005zbMath1387.90230arXiv1504.02151OpenAlexW2783589701MaRDI QIDQ1751254

Abraham P. Punnen, Tamon Stephen, Brad D. Woods

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingcombinatorial optimizationquadratic 0-1 programmingexact methodsquadratic travelling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions ⋮ Geometric and LP-based heuristics for angular travelling salesman problems in the plane ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem

Uses Software

• TSPLIB
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph
• Lower bounding procedure for the asymmetric quadratic traveling salesman problem
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• An extended approach for lifting clique tree inequalities
• Experimental analysis of heuristics for the bottleneck traveling salesman problem
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• The precedence-constrained asymmetric traveling salesman polytope
• The symmetric quadratic traveling salesman problem
• New facets of the STS polytope generated from known facets of the ATS polytope
• A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The traveling salesman problem in graphs with 3-edge cutsets
• On the Maximum Scatter Traveling Salesperson Problem
• Halin graphs and the travelling salesman problem
• The Angular-Metric Traveling Salesman Problem
• An Analysis of the Asymmetric Quadratic Traveling Salesman Polytope
• Minimization and maximization versions of the quadratic travelling salesman problem
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• In Pursuit of the Traveling Salesman

This page was built for publication: A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions