The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals

DOI10.1007/978-981-19-8152-4_5zbMATH Open1541.6844MaRDI QIDQ6535280

Yong Wang

Publication date: 2 December 2023

zbMATH Keywords

randomized algorithmtraveling salesman problembounded-degree graphfrequency quadrilateral

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Cites Work

• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals
• Certification of an optimal TSP tour through 85,900 cities
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• POPMUSIC for the travelling salesman problem
• The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem
• Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals
• A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
• A new upper bound for the traveling salesman problem in cubic graphs
• The traveling salesman problem and its variations.
• Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals
• The traveling salesman problem on cubic and subcubic graphs
• Tolerance-based branch and bound algorithms for the ATSP
• A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals
• Edge Elimination in TSP Instances
• The traveling salesman problem in bounded degree graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Special Frequency Quadrilaterals and an Application
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• On the Computational Complexity of Combinatorial Problems
• A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs
• An improved approximation algorithm for ATSP
• Polylogarithmic approximation for Euler genus on bounded degree graphs
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• TSP Tours in Cubic Graphs: Beyond 4/3
• The Traveling Salesman Problem for Cubic Graphs
• A (slightly) improved approximation algorithm for metric TSP
• An ETH-Tight Exact Algorithm for Euclidean TSP

Related Items (1)

Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals

This page was built for publication: The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals