Tour Merging via Branch-Decomposition

References

• Alon N. Eigenvalues and expanders. Combinatorica (1986) 6:83–96Crossref, Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. Finding cuts in the TSP (a preliminary report). (1995) . DIMACS Technical report 95-05, DIMACS, Rutgers University, New Brunswick, NJGoogle Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. On the solution of traveling salesman problems. Documenta Math. J. der Deutschen Mathematiker-Vereinigung, Internat. Congress of Math. (1998) 645–656Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W., Jünger M., Naddef D. TSP cuts which do not conform to the template paradigm. Computational Combinatorial Optimization (2001) (Springer-Verlag, Heidelberg, Germany) 261–304Crossref, Google Scholar
• Applegate D., Cook W., Rohe A. Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. on Comput. (2003) 15:82–92Link, Google Scholar
• Arnborg S., Lagergren J., Seese D. Easy problems for tree-decomposable graphs. J. Algorithms (1991) 12:308–340Crossref, Google Scholar
• Balas E., Simonetti N. Linear time dynamic programming algorithms for some new classes of restricted TSPs: A computational study. INFORMS J. on Comput. (2001) 13:56–75Link, Google Scholar
• Bern M. W., Lawler E. L., Wong A. L. Linear time computation of optimal subgraphs of decomposable graphs. J. Algorithms (1987) 8:216–235Crossref, Google Scholar
• Bodlaender H. L. A tourist guide through treewidth. Acta Cybernetica (1993) 11:1–21Google Scholar
• Bodlaender H. L. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. on Comput. (1996) 25:1305–1317Crossref, Google Scholar
• Bodlaender H. L. A partial k-arboretum of graphs with bounded treewidth. Theoretical Comput. Sci. (1998) 209:1–45Crossref, Google Scholar
• Bodlaender H. L., Kloks T. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms (1996) 21:358–402Crossref, Google Scholar
• Bodlaender H. L., Thilikos D. M., Degano P., Gorrieri R., Marchetti-Spaccamela A. Constructive linear time algorithms for branch-width. Proc. 24th Internat. Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science (1997) no. 1256(Springer-Verlag, Berlin, Germany) 627–637Crossref, Google Scholar
• Bodlaender H. L., Thilikos D. M. Graphs with branchwidth at most three. J. Algorithms (1999) 32:167–194Crossref, Google Scholar
• Borie R. B., Parker R. G., Tovey C. A. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica (1992) 7:555–581Crossref, Google Scholar
• Courcelle B. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Informat. Comput. (1990) 85:12–75Crossref, Google Scholar
• Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. (2000) 126:106–130The LKH code is available at http://www.dat.ruc.dk/~keld/research/LKH/Crossref, Google Scholar
• Hicks I. V. Branch decompositions and their applications. (2000) . Ph.D. thesis, Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Johnson D. S. Local optimization and the traveling salesman problem. Proc. 17th Colloquium of Automata, Languages, and Programming, Lecture Notes in Computer Science (1990) no. 443(Springer-Verlag, Berlin, Germany) 446–461Crossref, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The traveling salesman problem: A case study in local optimization. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, New York) 215–310Google Scholar
• Johnson D. S., McGeoch L. A., Gutin G., Punnen A. Experimental analysis of heuristics for the STSP. The Traveling Salesman Problem and Its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 369–443Google Scholar
• Koster A. M. C. A., Bodlaender H. L., van Hoesel S. P. M. Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics (2001) 8(Elsevier Science Publishers, Amsterdam, The Netherlands) Crossref, Google Scholar
• Koster A. M. C. A., van Hoesel S. P. M., Kolen A. W. J. Solving frequency assignment problems via tree-decomposition. Networks (2002) 40:170–180Crossref, Google Scholar
• Lagergren J. Efficient parallel algorithms for tree-decomposition and related problems. Proc. 31st Ann. Sympos. on the Foundations of Comput. Sci. (1990) (ACM Press, New York) 173–182Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Martin O. C., Otto S. W. Combining simulated annealing with local search heuristics. Ann. Oper. Res. (1996) 63:57–75Crossref, Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Matoušek J., Thomas R. Algorithms finding tree-decompositions of graphs. J. Algorithms (1991) 12:1–22Crossref, Google Scholar
• Reed B. Finding approximate separators and computing tree-width quickly. Proc. 24th Annual ACM Sympos. on the Theory of Comput (1992) (ACM Press, New York) 221–228Crossref, Google Scholar
• Reinelt G. TSPLIB—A traveling salesman problem library. ORSA J. on Comput. (1991) 3:376–384An updated version is available at http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/Link, Google Scholar
• Robertson N., Seymour P. D. Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory, Ser. B (1991) 52:153–190Crossref, Google Scholar
• Schilham R. M. F.Commonalities in Local Search (2001) . Ph.D. thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, The NetherlandsGoogle Scholar
• Seymour P. D., Thomas R. Call routing and the ratcather. Combinatorica (1994) 14:217–241Crossref, Google Scholar
• Tamaki H. Alternating cycles contribution: A tour merging strategy for the traveling salesman problem. (2003) . Research Report MPI-2003-1-007, Max-Planck-Institut für Informatik, Saarbrücken, GermanyGoogle Scholar
• Walshaw C. A multilevel approach to the travelling salesman problem. (2000) . Technical Report 01/IM/80, Computing and Mathematical Sciences Department, University of Greenwich, London, UKGoogle Scholar