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 QIDQ6535280FDOQ6535280

Authors: 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) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Cites Work

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

Cited In (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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535280)