Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane

DOI10.1016/j.ejor.2018.03.042zbMath1403.90567arXiv1512.06649OpenAlexW2285115199MaRDI QIDQ1651693

Hadrien Cambazard, Nicolas Catusse

Publication date: 12 July 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.06649

zbMATH Keywords

traveling salesmanfixed-parameter algorithmrectilinear Steiner tree problemrectilinear traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

The joint order batching and picker routing problem: modelled and solved as a clustered vehicle routing problem, An efficient and general approach for the joint order batching and picker routing problem, Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses, Exact algorithms for the order picking problem, The forgotten sons: warehousing systems for brick-and-mortar retail chains

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact formulations of the Steiner traveling salesman problem and related problems
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Optimally solving the joint order batching and picker routing problem
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Tour Merging via Branch-Decomposition
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• The Rectilinear k-Bends TSP
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The n-line traveling salesman problem
• Rectilinear steiner trees: Efficient special-case algorithms
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Hamilton Paths in Grid Graphs
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• Multiplying matrices faster than coppersmith-winograd
• Routing order pickers in a warehouse with a middle aisle