The traveling salesman problem in bounded degree graphs
From MaRDI portal
Publication:3189059
DOI10.1145/2151171.2151181zbMath1295.90060OpenAlexW2012438638MaRDI QIDQ3189059
Mikko Koivisto, Petteri Kaski, Thore Husfeldt, Andreas Björklund
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
dynamic programmingtraveling salesman problempermanenttrimminginclusion-exclusionShearer's entropy lemma
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)
Related Items (19)
On the number of connected sets in bounded degree graphs ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Extremal problems for connected set enumeration ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals ⋮ The shape of node reliability ⋮ Special Frequency Quadrilaterals and an Application ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ A new upper bound for the traveling salesman problem in cubic graphs ⋮ Enumerating simple paths from connected induced subgraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Faster exponential-time algorithms in graphs of bounded average degree ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
This page was built for publication: The traveling salesman problem in bounded degree graphs
