The traveling salesman problem in bounded degree graphs
DOI10.1145/2151171.2151181zbMATH Open1295.90060OpenAlexW2012438638MaRDI QIDQ3189059FDOQ3189059
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
Recommendations
trimmingdynamic programmingtraveling salesman problempermanentinclusion-exclusionShearer's entropy lemma
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)
Cited In (29)
- Special frequency quadrilaterals and an application
- 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
- Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals
- Extremal problems for connected set enumeration
- Title not available (Why is that?)
- A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
- The shape of node reliability
- Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour
- Enumerating simple paths from connected induced subgraphs
- Title not available (Why is that?)
- Faster exponential-time algorithms in graphs of bounded average degree
- 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
- 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
- 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
- The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
- On the number of connected sets in bounded degree graphs
- 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
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Solving target set selection with bounded thresholds faster than \(2^n\)
- The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem
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)
