Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs

-

Saved in:
Bibliographic Details
Main Author: Md Yunos, Norhazwani
Format: Thesis
Language:English
Published: 2017
Subjects:
Online Access:http://eprints.utem.edu.my/id/eprint/19056/1/Polynomial-Space%20Exact%20Algorithms%20For%20Traveling%20Salesman%20Problem%20In%20Degree%20Bounded%20Graphs.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-utem-ep.19056
record_format uketd_dc
institution Universiti Teknikal Malaysia Melaka
collection UTeM Repository
language English
topic Q Science (General)
QA Mathematics
spellingShingle Q Science (General)
QA Mathematics
Md Yunos, Norhazwani
Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
description -
format Thesis
qualification_name Doctor of Philosophy (PhD.)
qualification_level Doctorate
author Md Yunos, Norhazwani
author_facet Md Yunos, Norhazwani
author_sort Md Yunos, Norhazwani
title Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
title_short Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
title_full Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
title_fullStr Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
title_full_unstemmed Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs
title_sort polynomial-space exact algorithms for traveling salesman problem in degree bounded graphs
granting_institution Universiti Teknikal Malaysia Melaka
granting_department Faculty Of Mechanical Engineering
publishDate 2017
url http://eprints.utem.edu.my/id/eprint/19056/1/Polynomial-Space%20Exact%20Algorithms%20For%20Traveling%20Salesman%20Problem%20In%20Degree%20Bounded%20Graphs.pdf
_version_ 1747833960816181248
spelling my-utem-ep.190562021-01-05T16:30:43Z Polynomial-Space Exact Algorithms For Traveling Salesman Problem In Degree Bounded Graphs 2017 Md Yunos, Norhazwani Q Science (General) QA Mathematics - 2017 Thesis http://eprints.utem.edu.my/id/eprint/19056/ http://eprints.utem.edu.my/id/eprint/19056/1/Polynomial-Space%20Exact%20Algorithms%20For%20Traveling%20Salesman%20Problem%20In%20Degree%20Bounded%20Graphs.pdf text en public https://plh.utem.edu.my/cgi-bin/koha/opac-detail.pl?biblionumber=102972 phd doctoral Universiti Teknikal Malaysia Melaka Faculty Of Mechanical Engineering 1. Akiba, T., Iwata, Y. : Branch-and-reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover. In: Theoretical Computer Science, Vol. 609, Part 1, pp. 211{225 (2016) 2. Angel, R. D., Caudle, W. L., Noonan, R., Whinston, A. : Computer-Assisted School Bus Scheduling. In: Management Science, Vol. 18, No. 6, pp. B279{B288 (1972) 3. Arora, S. : PTAS for Euclidean Traveling Salesman and Other Geometric Problems. In: Journal of the ACM, Vol. 45, No. 5, pp. 753{782 (1998) 4. Asadpour, A., Goemans, M. X., Madry, A., Oveis Gharan, S., Saberi, A. : An O(log n= log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 379{389 (2010) 5. Basart, J. M., Huguet, L. : An Approximation Algorithm for the TSP. In: Information Processing Letters, Vol. 31, pp. 77{81 (1989) 6. Bellman, R. : Combinatorial Processes and Dynamic Programming. In: Proceedings of the 10th Symposium in Applied Mathematics, Amer. Math. Soc., Providence, RI,(1960) 7. Berman, P., Karpinski, M. : 87-approximation Algorithm for (1; 2)-TSP. In: Pro-ceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2006), pp. 641{648 (2006) 8. Bland, R. E., Shallcross, D. E. : Large Traveling Salesman Problem Arising from Experiments in X-ray Crystallography: A Preliminary Report on Computation. In: Operations Research Letters, Vol. 8, No. 3, pp. 125{128 (1989) 9. Blaser, M. : A New Approximation Algorithm for the Asymmetric TSP with triangle inequality. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 638{645 (2003) 10. Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J. : Deterministic Single Expo-nential Time Algorithms for Connectivity Problems Parameterized by Treewidth. In: Information and Computation, Vol. 243, pp. 86{111 (2015) 11. Christodes, N. : Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem. In: Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976) 12. Cook, S. A. : The Complexity of Theorem-Proving Procedures. In: Proceedings of 3rd Annual ACM Symposium Theory of Computing, pp. 151{158 (1971) 13. Cook, W. J. : In Pursuit of the Traveling Salesman Problem. Princeton University Press (2012) 14. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. : Introduction to Algorithms. The MIT press (2009) 15. Dantzig, G. B., Fulkerson, D. R., Johnson, S. M. : Solution of a Large Scale Traveling- Salesman Problem. In: Operations Research, Vol. 2, pp. 393{410 (1954) 16.Dasgupta, S., Papadimitriou, C., Vazirani, U. : Algorithms. McGraw Hill Higher Education (2006) 17. Eppstein, D. : Quasiconvex Analysis of Backtracking Algorithms. In: Proceedings of The 15th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA 2004), ACM Press, pp. 781{790 (2004) 18.Eppstein, D. : The Traveling Salesman Problem for Cubic Graphs. In: Journal of Graph Algorithms and Applications, Vol. 11, No. 1, pp. 61{81 (2007) 19. Fomin, F. V., Grandoni, F, Kratsch, D. : A Measure and Conquer Approach for the Analysis of Exact Algorithms. In: Journal of the ACM, Vol. 56, No. 6, Article 25 (2009) 20. Fomin, F. V., Kratsch, D. : Exact Exponential Algorithms. Springer (2010) 21. Garey, M. R., Johnson, D. S. : Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979) 22. Gebauer, H. : Finding and Enumerating Hamilton Cycles in 4-regular Graphs. In: Theoretical Computer Science, Vol. 412, No. 35, pp. 4579{4591 (2011) 23. Giorgi, G., Guerraggio, A., Thierfelder, J. : Mathematics of Optimization: Smooth and Nonsmooth Case. Elsevier (2004) 24. Grotschel, M., Junger, M., Reinelt, G. : Optimal Control of Plotting and Drilling Machines: A Case Study. In: Mathematical Methods of Operations Research, Vol. 35, No. 1, pp. 61{84 (1991) 25. Gurevich, Y., Shelah, S. : Expected Computation Time for Hamiltonian Path Problem. In: SIAM Journal on Computing, Vol. 16, No. 3, pp. 486{502 (1987) 26. Held, M., Karp, R. M. : A Dynamic Programming Approach to Sequencing Problems. In: Journal of the Society for Industrial and Applied Mathematics (SIAM), Vol. 10, No. 1, pp. 196{210 (1962) 27. Iwama, K., Nakashima, T. : An Improved Exact Algorithm for Cubic Graph TSP. In: Computing and Combinatorics, Lecture Notes in Computer Science, Vol. 4598, pp. 108{117 (2007) 28. Johnson, D. S., McGeoch, L. A., Rothberg, E. E. : Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. In: Proceedings of the Annual ACM- SIAM Symposium on Discrete Algorithms, pp. 341{350 (1996) 29. Junger, M., Reinelt, G., Rinaldi, G. : The Traveling Salesman Problem. In: Hand- books in Operations Research and Management Science, Vol. 7, Chapter 4, pp. 225{330 (1995) 30. Jungnickel, D. : Graphs, Networks and Algorithms. Springer (2005) 31. Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M. : Approximation Algorithms for Asymmetric TSP by decomposing Directed Regular Multigraphs. In: Journal of the ACM, Vol. 52, pp. 602{626 (2005) 32. Laporte, G. : The Traveling Salesman Problem: An Overview of Exact and Approxi-mate Algorithms. In: European Journal of Operational Research, Vol. 59, pp. 231{247 (1992) 33. Lenstra, J. K., Rinnooy Kan, A. H. G. : Some Simple Applications of the Traveling Salesman Problem. In: Journal of the Operational Research Society (JORS), Vol. 26, No. 4, pp. 717{733 (1975) 34. Lin, S., Kernighan, B. W. : An Eective Heuristic Algorithm for the Traveling Sales-man Problem. In: Operations Research, Vol. 21, No. 2, pp. 498{516 (1973) 35. Liskiewicz, M., Schuster, M.R. : A New Upper Bound for the Traveling Salesman Problem in Cubic Graphs. In: Journal of Discrete Algorithms, Vol. 27, pp. 1{20 (2014) 36. Md Yunos, N., Shurbevski, A., Nagamochi, H. : A Polynomial-space Exact Algorithm for TSP in Degree-5 Graphs. In: Proceedings of the 12th International Symposium on Operations Research and Its Applications in Engineering, Technology and Man- agement (ISORA 2015), pp. 45{58 (2015) 37. Md Yunos, N., Shurbevski, A., Nagamochi, H. : A Polynomial-space Exact Algorithm for TSP in Degree-6 Graphs. In: Discrete and Computation Geometry and Graphs, Lecture Notes in Computer Science, Vol. 9943, pp. 228{240 (2016) 38. Md Yunos, N., Shurbevski, A., Nagamochi, H. : A Polynomial-space Exact Algorithm for TSP in Degree-7 Graphs. In: Proceedings of the 9th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2016), pp. 49 (2016) 39. Md Yunos, N., Shurbevski, A., Nagamochi, H. : A Polynomial-space Exact Algorithm for TSP in Degree-8 Graphs. In: Proceedings of the 19th Japan-Korea JointWorkshop on Algorithms and Computation (WAAC 2016), Session 1, Talk 3 (2016) 40. Mucha, M. : 13 9 -approximation for Graphic TSP. In: Proceedings of the 29th Inter-national Symposium on Theoretical Aspects of Computer Science, pp. 30{41 (2012) 41. Papadimitriou, C. H., Vempala, S. : On the Approximability of Traveling Salesman Problem. In: Combinatorica, Vol. 26, No. 1, pp. 101{120 (2006) 42. Ratli, H. D., Rosenthal, A. S. : Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem. In: Operations Research, Vol. 31, No. 3, pp. 507{521 (1983) 43. Rubin, F. : A Search Procedure for Hamilton Paths and Circuits. In: Journal of the ACM, Vol. 21, No. 4, pp. 576{580 (1974) 44. Schrijver, A. : Theory of Linear and Integer Programming. John Wiley & Sons (1998) 45. Sedgewick, R. : Algorithms in C. Addison-Wesley (2014) 46. Vazirani, V. V. : Approximation Algorithms. Springer (2001) 47. Vygen, J. : New Approximation Algorithms for the TSP. In: Optima: Mathematical Optimization Society Newsletter, Vol. 90 (2012) 48. Williamson, D. P., Shmoys, D. B. : The Design of Approximation Algorithms. Cam-bridge University Press (2011). 49. Xiao, M., Nagamochi, H. : An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure. In: Algorithmica, Vol.74, No. 2, pp. 713{741 (2016) 50. Xiao, M., Nagamochi, H. : An Improved Exact Algorithm for the TSP in Graphs of Maximum Degree 4. In: Theory of Computing Systems, Vol. 58, No. 2, pp. 241{272 (2016) 51. Xiao, M., Nagamochi, H. : Exact Algorithms for Maximum Independent Set. In: Algorithms and Computation, Lecture Notes in Computer Science, Vol. 8283, pp.328{338 (2013)