The traveling salesman problem in bounded degree graphs

DOI10.1145/2151171.2151181MaRDI QIDQ3189059zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2151171.2151181

zbMATH Keywords

trimmingdynamic programmingtraveling salesman problempermanentinclusion-exclusionShearer's entropy lemma

Mathematics Subject Classification ID

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

Recommendations

• The Travelling Salesman Problem in Bounded Degree Graphs
• Faster exponential-time algorithms in graphs of bounded average degree
• The traveling salesman problem for cubic graphs.
• An Improved Exact Algorithm for Cubic Graph TSP
• An improved exact algorithm for TSP in graphs of maximum degree 4

Cited in

(28)

• An improved exact algorithm for TSP in graphs of maximum degree 4
• Special frequency quadrilaterals and an application
• Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals
• Extremal problems for connected set enumeration
• The shape of node reliability
• Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour
• scientific article; zbMATH DE number 4191425 (Why is no real title available?)
• A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
• Enumerating simple paths from connected induced subgraphs
• Faster exponential-time algorithms in graphs of bounded average degree
• scientific article; zbMATH DE number 7559398 (Why is no real title available?)
• Faster exponential-time algorithms in graphs of bounded average degree
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• A new upper bound for the traveling salesman problem in cubic graphs
• Exploiting sparsity for bipartite Hamiltonicity
• Approximate and randomized algorithms for computing a second Hamiltonian cycle
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• On the Number of Connected Sets in Bounded Degree Graphs
• The graphical traveling salesperson problem has no integer programming formulation in the original space
• On the number of connected sets in bounded degree graphs
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals
• The Travelling Salesman Problem in Bounded Degree Graphs
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• The analyst's traveling salesman theorem in graph inverse limits
• The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)

This page was built for publication: The traveling salesman problem in bounded degree graphs

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