On polynomial kernels for traveling salesperson problem and its generalizations
From MaRDI portal
Cites work
- \(\frac {13}{9}\)-approximation for graphic TSP
- A completeness theory for polynomial (Turing) kernelization
- A method for solving traveling-salesman problems
- A Randomized Rounding Approach to the Traveling Salesman Problem
- A subexponential parameterized algorithm for subset TSP on planar graphs
- Algorithmic strategies for a fast exploration of the TSP 4-OPT neighborhood
- An application of simultaneous diophantine approximation in combinatorial optimization
- An improved approximation algorithm for TSP in the half integral case
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Approximating Graphic TSP by Matchings
- Approximation hardness of Travelling Salesman via weighted amplifiers
- Brief announcement: Treewidth modulator: emergency exit for DFVS
- Data reduction for graph coloring problems
- Deterministic APSP, Orthogonal Vectors, and More
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
- Fine-grained Complexity Analysis of Two Classic TSP Variants
- Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
- Graph theory
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1306896 (Why is no real title available?)
- scientific article; zbMATH DE number 1082106 (Why is no real title available?)
- scientific article; zbMATH DE number 2064412 (Why is no real title available?)
- scientific article; zbMATH DE number 1445294 (Why is no real title available?)
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions
- Intractability of clique-width parameterizations
- On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
- On the complexity of k-SAT
- On the complexity of some colorful problems parameterized by treewidth
- On the parameterized complexity of the connected flow and many visits TSP problem
- P-Complete Approximation Problems
- Parameterized algorithms
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Parameterized complexity of vertex colouring
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- The parameterized complexity of local search for TSP, more refined
- The traveling salesman problem and its variations.
- The traveling salesman problem on a graph and some related integer polyhedra
- The Traveling Salesman Problem with Distances One and Two
- The traveling-salesman problem and minimum spanning trees: Part II
- Towards improving Christofides algorithm for half-integer TSP
- Walking through waypoints
- Waypoint routing on bounded treewidth graphs
- Worst-case comparison of valid inequalities for the TSP
Cited in
(2)
This page was built for publication: On polynomial kernels for traveling salesperson problem and its generalizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969664)
