The Traveling Salesman Problem for Cubic Graphs

DOI10.7155/JGAA.00137zbMATH Open1161.68662DBLPjournals/jgaa/Eppstein07OpenAlexW2508797883WikidataQ56032468 ScholiaQ56032468MaRDI QIDQ5301405FDOQ5301405

Authors: David Eppstein 

Publication date: 19 January 2009

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/55409

Recommendations

• The traveling salesman problem for cubic graphs.
• An Improved Exact Algorithm for Cubic Graph TSP
• On the number of Hamilton cycles in bounded degree graphs
• Cubic TSP: A 1.3-Approximation
• A new upper bound for the traveling salesman problem in cubic graphs

zbMATH Keywords

minimum weight Hamiltonian cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cited In (35)

• Special frequency quadrilaterals and an application
• An improved exact algorithm for TSP in graphs of maximum degree 4
• Computing optimal Steiner trees in polynomial space
• A linear-size conversion of HCP to 3HCP
• Finding and enumerating Hamilton cycles in 4-regular graphs
• A travelling salesman problem in the \(k\)-dimensional unit cube
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
• Spotting trees with few leaves
• Spotting trees with few leaves
• Parameterized traveling salesman problem: beating the average
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Title not available (Why is that?)
• Approximate and randomized algorithms for computing a second Hamiltonian cycle
• A new upper bound for the traveling salesman problem in cubic graphs
• Exploiting sparsity for bipartite Hamiltonicity
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• Switching 3-edge-colorings of cubic graphs
• Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
• Three value TSP and linkages with the three value linear spanning 2-forests
• A new heuristic for detecting non-Hamiltonicity in cubic graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• The traveling salesman problem for cubic graphs.
• Heuristic search for Hamilton cycles in cubic graphs
• Finding 2-factors closer to TSP tours in cubic graphs
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• On the minimum number of Hamiltonian cycles in regular graphs
• On the number of Hamilton cycles in bounded degree graphs
• The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem

This page was built for publication: The Traveling Salesman Problem for Cubic Graphs

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