The parameterized complexity of local search for TSP, more refined
From MaRDI portal
(Redirected from Publication:378245)
heuristicsfixed-parameter tractabilityNP-hard problemlower bounds based on ETHproblem kernelW[1-hardness]
Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)
Recommendations
Cites work
- scientific article; zbMATH DE number 1082106 (Why is no real title available?)
- scientific article; zbMATH DE number 2064409 (Why is no real title available?)
- scientific article; zbMATH DE number 2064412 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Dynamic Programming Approach to Sequencing Problems
- A partial k-arboretum of graphs with bounded treewidth
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- Can you beat treewidth?
- Combinatorics of genome rearrangements.
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Incremental list coloring of graphs, parameterized by conservation
- Kernelization -- preprocessing with a guarantee
- Kernelization: new upper and lower bound techniques
- Local search: is brute-force avoidable?
- Lower bounds based on the exponential time hypothesis
- New classes of efficiently solvable generalized traveling salesman problems
- On problems without polynomial kernels
- On the hardness of losing weight
- On the parameterized complexity of multiple-interval graph problems
- Parametrized complexity theory.
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Reflections on multivariate algorithmics and problem parameterization
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- Stable assignment with couples: parameterized complexity and local search
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- The traveling salesman problem and its variations
- Tight lower bounds for certain parameterized NP-hard problems
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Which problems have strongly exponential complexity?
- Worst-case analysis of a new heuristic for the travelling salesman problem
Cited in
(15)- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- Fine-grained Complexity Analysis of Two Classic TSP Variants
- Parameterized Dynamic Cluster Editing
- Searching for better fill-in
- Parameterized dynamic cluster editing
- Methods for determining cycles of a specific length in undirected graphs with edge weights
- On the parameterized complexity of consensus clustering
- scientific article; zbMATH DE number 5859273 (Why is no real title available?)
- A subexponential parameterized algorithm for subset TSP on planar graphs
- The parameterized complexity of local search for TSP, more refined
- Fundamentals of Computation Theory
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Improving TSP tours using dynamic programming over tree decompositions
- Can local optimality be used for efficient data reduction?
- Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
This page was built for publication: The parameterized complexity of local search for TSP, more refined
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378245)
