The parameterized complexity of local search for TSP, more refined
DOI10.1007/S00453-012-9685-8zbMATH Open1292.68086OpenAlexW2113885662MaRDI QIDQ378245FDOQ378245
Authors: Jiong Guo, Sepp Hartung, Rolf Niedermeier, Ondřej Suchý 
Publication date: 11 November 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9685-8
Recommendations
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)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- A Dynamic Programming Approach to Sequencing Problems
- On problems without polynomial kernels
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- The traveling salesman problem and its variations
- Parametrized complexity theory.
- Kernelization -- preprocessing with a guarantee
- Can you beat treewidth?
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Lower bounds based on the exponential time hypothesis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Worst-case analysis of a new heuristic for the travelling salesman problem
- Combinatorics of genome rearrangements.
- On the parameterized complexity of multiple-interval graph problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Stable assignment with couples: parameterized complexity and local search
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- Reflections on multivariate algorithmics and problem parameterization
- Tight lower bounds for certain parameterized NP-hard problems
- Kernelization: new upper and lower bound techniques
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- New classes of efficiently solvable generalized traveling salesman problems
- On the hardness of losing weight
- Incremental list coloring of graphs, parameterized by conservation
- Local search: is brute-force avoidable?
- Title not available (Why is that?)
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
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
- A subexponential parameterized algorithm for subset TSP on planar graphs
- Title not available (Why is that?)
- 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
- Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
- Can local optimality be used for efficient data reduction?
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)
