{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:51:29Z","timestamp":1760151089115,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In time-evolving graphs, the graph changes at each time interval, and the previously computed results become invalid. We addressed this issue for the traveling salesman problem (TSP) in our previous work and proposed an incremental algorithm where the TSP tour is computed from the previous result instead of the whole graph. In our current work, we have mapped the TSP problem to three partitioning methods named vertex size attribute, edge attribute, and k-means; then, we compared the TSP tour results. We have also examined the effect of increasing the number of partitions on the total computation time. Through our experiments, we have observed that the vertex size attribute performs the best because of a balanced number of vertices in each partition.<\/jats:p>","DOI":"10.3390\/a15020064","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T20:26:42Z","timestamp":1644870402000},"page":"64","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Accelerate Incremental TSP Algorithms on Time Evolving Graphs with Partitioning Methods"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0039-8878","authenticated-orcid":false,"given":"Shalini","family":"Sharma","sequence":"first","affiliation":[{"name":"Institute of Information System and Applications, National Tsing Hua University, Hsinchu City 300, Taiwan"}]},{"given":"Jerry","family":"Chou","sequence":"additional","affiliation":[{"name":"Institute of Information System and Applications, National Tsing Hua University, Hsinchu City 300, Taiwan"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An Effective Heuristic Algorithm for the Traveling-Salesman Problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Rosenkrantz, D.J., Stearns, R.E., and Lewis, P.M. (1974, January 14\u201316). Approximate Algorithms for the Traveling Salesperson Problem. Proceedings of the 15th Annual Symposium on Switching and Automata Theory (Swat 1974), New Orleans, LA, USA.","DOI":"10.1109\/SWAT.1974.4"},{"key":"ref_3","first-page":"307","article-title":"Robot Path Planning Based on the Travelling Salesman Problem","volume":"46","author":"Wang","year":"2015","journal-title":"Chem. Eng. Trans."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/j.apm.2021.08.030","article-title":"Coupled orbit-attitude dynamics and trajectory tracking control for spacecraft electromagnetic docking","volume":"101","author":"Shi","year":"2022","journal-title":"Appl. Math. Model."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"107053","DOI":"10.1016\/j.ast.2021.107053","article-title":"Are nonfragile controllers always better than fragile controllers in attitude control performance of post-capture flexible spacecraft?","volume":"118","author":"Liu","year":"2021","journal-title":"Aerosp. Sci. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Liu, C., Yue, X., Zhang, J., and Shi, K. (2021). Active Disturbance Rejection Control for Delayed Electromagnetic Docking of Spacecraft in Elliptical Orbits. IEEE Trans. Aerosp. Electron. Syst., 1.","DOI":"10.1109\/TAES.2021.3130830"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hoffman, K.L., Padberg, M., and Rinaldi, G. (2013). Traveling Salesman Problem. Encyclopedia of Operations Research and Management Science, Springer.","DOI":"10.1007\/978-1-4419-1153-7_1068"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","article-title":"The clustered traveling salesman problem","volume":"2","author":"Chisman","year":"1975","journal-title":"Comput. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cosma, O., Pop, P.C., and Cosma, L. (2021). An effective hybrid genetic algorithm for solving the generalized traveling salesman problem. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/978-3-030-86271-8_10"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Pop, P.C., Matei, O., and Sabo, C. (2010). A New Approach for Solving the Generalized Traveling Salesman Problem. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/978-3-642-16054-7_5"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1016\/j.pnsc.2008.03.028","article-title":"Ant colony optimization method for generalized TSP problem","volume":"18","author":"Yang","year":"2008","journal-title":"Prog. Nat. Sci."},{"key":"ref_12","unstructured":"Junjie, P., and Dingwei, W. (September, January 30). An Ant Colony Optimization Algorithm for Multiple Travelling Salesman Problem. Proceedings of the First International Conference on Innovative Computing, Information and Control\u2013Volume I (ICICIC\u201906), Beijing, China."},{"key":"ref_13","unstructured":"Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, University of Michigan Press."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"10896","DOI":"10.1007\/s11227-021-03716-5","article-title":"Distributed and incremental travelling salesman algorithm on time-evolving graphs","volume":"77","author":"Sharma","year":"2021","journal-title":"J. Supercomput."},{"key":"ref_15","unstructured":"Sharma, S., and Chou, J. (2010, January 12\u201316). Partitioning based incremental travelling salesman algorithm on time evolving graphs. Proceedings of the PDPTA\u201921: Parallel & Distributed Processing Techniques & Applications, Las Vegas, NV, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Luo, J., Tan, Z., Wang, X., and Wu, Y. (2011, January 12\u201316). Incremental Graph Pattern Matching. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece.","DOI":"10.1145\/1989323.1989420"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kao, J.S., and Chou, J. (2016, January 31). Distributed Incremental Pattern Matching on Streaming Graphs. Proceedings of the ACM Workshop on High Performance Graph Processing, Kyoto, Japan.","DOI":"10.1145\/2915516.2915519"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Desikan, P., Pathak, N., Srivastava, J., and Kumar, V. (2005, January 10\u201314). Incremental Page Rank Computation on Evolving Graphs. Proceedings of the Special Interest Tracks and Posters of the 14th International Conference on World Wide Web, Chiba, Japan.","DOI":"10.1145\/1062745.1062885"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Kumar, R., Mahdian, M., and Upfal, E. (2012, January 12\u201316). PageRank on an Evolving Graph. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China.","DOI":"10.1145\/2339530.2339539"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Kumar, R., Mahdian, M., Upfal, E., and Vandin, F. (2012, January 8\u201310). Algorithms on Evolving Graphs. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, MA, USA.","DOI":"10.1145\/2090236.2090249"},{"key":"ref_21","first-page":"1","article-title":"A survey of computation techniques on time evolving graphs","volume":"7","author":"Sharma","year":"2020","journal-title":"Int. J. Big Data Intell. (IJBDI)"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Shang, Y. (2015). Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0123426"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Abdolrashidi, A., and Ramaswamy, L. (July, January 27). Continual and Cost-Effective Partitioning of Dynamic Graphs for Optimizing Big Graph Processing Systems. Proceedings of the 2016 IEEE International Congress on Big Data (BigData Congress), San Francisco, CA, USA.","DOI":"10.1109\/BigDataCongress.2016.12"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Gkantsidis, C., Radunovic, B., and Vojnovic, M. (2014, January 24\u201328). FENNEL: Streaming Graph Partitioning for Massive Scale Graphs. Proceedings of the 7th ACM International Conference on Web Search and Data Mining, New York, NY, USA.","DOI":"10.1145\/2556195.2556213"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Chen, P. (2013, January 23\u201325). An improved genetic algorithm for solving the Traveling Salesman Problem. Proceedings of the 2013 Ninth International Conference on Natural Computation (ICNC), Shenyang, China.","DOI":"10.1109\/ICNC.2013.6818008"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man Cybern. Part B (Cybernetics)"},{"key":"ref_28","unstructured":"Kennedy, J., and Eberhart, R. (December, January 27). Particle swarm optimization. Proceedings of the ICNN\u201995\u2014International Conference on Neural Networks, Perth, WA, Australia."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Glover, F., and Laguna, M. (1999). Tabu Search I, Springer.","DOI":"10.1007\/978-1-4613-0303-9_33"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"98","DOI":"10.4236\/jcc.2016.415009","article-title":"Solving Travelling Salesman Problem with an Improved Hybrid Genetic Algorithm","volume":"4","author":"Lin","year":"2016","journal-title":"J. Comput. Commun."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Valenzuela, C. (1995, January 12\u201314). A parallel implementation of evolutionary divide and conquer for the TSP. Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, Sheffield, UK.","DOI":"10.1049\/cp:19951098"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Gu, Y., Shun, J., and Sun, Y. (2020, January 15\u201317). Randomized Incremental Convex Hull is Highly Parallel. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event.","DOI":"10.1145\/3350755.3400255"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"338","DOI":"10.14778\/3157794.3157802","article-title":"Effective and Efficient Dynamic Graph Coloring","volume":"11","author":"Yuan","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.14778\/3389133.3389142","article-title":"Incrementalization of Graph Partitioning Algorithms","volume":"13","author":"Fan","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"ref_35","unstructured":"Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., and Guestrin, C. (2012, January 8\u201310). PowerGraph: Distributed Graph-parallel Computation on Natural Graphs. Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, Hollywood, CA, USA."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Filippidou, I., and Kotidis, Y. (November, January 29). Online and on-demand partitioning of streaming graphs. Proceedings of the 2015 IEEE International Conference on Big Data (Big Data), Santa Clara, CA, USA.","DOI":"10.1109\/BigData.2015.7363735"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Salihoglu, S., and Widom, J. (2013, January 29\u201331). GPS: A Graph Processing System. Proceedings of the 25th International Conference on Scientific and Statistical Database Management, Baltimore, MD, USA.","DOI":"10.1145\/2484838.2484843"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/64\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:19:22Z","timestamp":1760134762000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,14]]},"references-count":37,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020064"],"URL":"https:\/\/doi.org\/10.3390\/a15020064","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,14]]}}}