Ant algorithms for finding weighted and unweighted maximum cliques in d-division graphs

• Autorzy: Schiff, Krzysztof
• Języki publikacji: EN

Abstrakty

EN

This article deals with the problem of finding the maximum number of maximum cliques in a weighted graph with all edges between vertices from different d-division of a graph with the minimum total weight of all these cliques, and the problem of finding the maximum number of maximum cliques in a non-weighted graph with not all edges between vertices from different d-division of the graph. This article presents new ant algorithms with new desire functions for these problems. These algorithms were tested for their purpose with different changing input parameters, the test results were tabulated and discussed, the best algorithms were indicated.

Słowa kluczowe

EN

d-division graph; ant algorithm; maximum clique; machine control; object tracking

• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 2
• Strony: 381--387
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Schiff, Krzysztof

• Cracow University of Technology, Poland,

Bibliografia

• [1] A. Dehgan, S.M. Assari, M. Shah, “GMMCP Tracker: Globally Optimal Generalized Maximum Multi Clique Problem for Multiple Object Tracking”, Conference on Computer Vision and Pattern Recognition, pp. 4091-4099, 2015.
• [2] L. Wen, Z. Lei, S. Lyu, S. Z. Li, M. Yang, “Exploiting hierarchical dense structures on hyper-graphs for multi-object tracking”, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 38, no. 10, pp. 1983-1996, 2016.
• [3] A. R. Zamir, A. Dehghan, M. Shah, “GMCP-tracker: global multi-object tracking using generalized minimum clique graphs”, in European Conference on Computer Vision, 2012.
• [4] W. Liu, O. Camps, M. Sznaier, “Multi-camera multi-object tracking” in Computer Vision and Pattern Recognition, arXiv:1709.07065, pp. 1-7, 2017.
• [5] T. Grunert, S. Irnich, H.J. Zimmermann, M. Schneider, B. Wulfhorst, “Finding all k-cliques in k-partite graph, an application in textile engineering”, Computer and Operation Research, vol. 29, no. 2, pp. 13-31, 2002.
• [6] M. Mirghorbani, P. Krokhmal, “On finding k-cliques in k-partite graphs”, Optimization Letters, vol 7, pp. 1155 -1165, 2013.
• [7] D. Deb, M. Yeddanapudi, K. PattiPati, T. A. Bar-Shalom, “A generalized S-D assignment algorithm for multi-sensor-multitarget state estimation”, IEEE Transactions on Aerospace and Electronic Systems, vol. 33, pp. 523-538, 1999.
• [8] C. Feremans, M. Labbe, G. Laportee, “Generalized network design problem”, European Journal of Operational Research, vol. 148, pp. 1-13, 2003.
• [9] A. M .C. A. Koster, S. P. M. Hoesel, A. W. J. Kolen, “The partial constraint satisfaction problem: Facets and lifting theorems”, Operation Research Letters, vol. 23, pp. 89-97, 1998.
• [10] K. Yoon, D.Y. Kim, Y.C. Yoon, M. Jeon, “Data association for Multi-Object Tracking via Deep Neural Networks”, Sensors, vol. 19, no. 3, pp. 1-17, 2019.
• [11] B. Lee, E. Erdenee, S. Jin, P .K. Rhee, “Efficient object detection using convolutional neural network-based hierarchical feature modeling”, Image Video Proc., vol. 10, no. 8, pp. 1503-1510, 2016.
• [12] J. Kennedy, R. Eberhart, “Particle swarm optimization” in Proc. IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, 1995.
• [13] G. Chen, L. Hong, “A genetic based multi-dimensional data association algorithm for multi sensor multi target tracking”, Mathematical Computing Models, vol. 26, pp. 57-69, 1997.
• [14] I. A. Temitope, S. Patrick Sebastian, I. I. Lila, I. Oladimeji, S. A. Lukman, A. B. Abdulrahman, B. Abubakar, A. S. Yau, “Multi-camera multi-object tracking: A review of current trends and future advances”, Neurocomputing, no. 552, pp. 1-32, 2023.
• [15] W. Luo, J. Xing, A. Milan, X. Zhang, W. Liu, T. K. Kim, “Multiple object tracking: A literature review”, Artificial Intelligence, no. 293, pp. 1-23, 2021.
• [16] Ch. Qiu, Z. Zhang, H. Lu, H. Luo, “A survey of motion-based multi-target tracking methods”, Progress in Electro-magnetic Research, no. 62, pp. 195-223. 2015.
• [17] A. O. Bozdogan, M. Efe, “Improved assignment with ant colony optimization for multi-target tracking”, Expert Systems with Applications, no. 38, pp. 9172-9178, 2011.
• [18] A. O. Bozdogan, M. Efe, “Ant Colony Optimization Heuristic for the multidimensional assignment problem in target tracking”, IEEE National Radar Conference, 2008.
• [19] K. Schiff, “Ant colony optimization for object identification in multi-cameras video tracking systems” in New advances in dependability of networks and systems, Seventeenth International Conference on Dependability of Computer Systems: DepCoS-RELCOMEX, June 27-July 1, Wrocław, Poland, 2022.
• [20] K. Schiff, “Partitioning of an M-Part Weighted Graph with N Vertices in Each Part into N Cliques with M Vertices and the Total Minimum Sum of Their Edges Weights Using Ant Algorithms”, in: Zamojski, W., Mazurkiewicz, J., Sugier, J., Walkowiak, T., Kacprzyk, J. (eds) Dependable Computer Systems and Networks. DepCoS-RELCOMEX 2023. Lecture Notes in Networks and Systems, vol 737. Springer, Cham. https://doi.org/10.1007/978-3-031-37720-4_24.
• [21] K. Schiff, “Ant Colony Optimization Algorithm for Finding the Maximum Number of d-Size Cliques in a Graph with Not All m Edges between Its d Parts”, in: Zamojski, W., Mazurkiewicz, J., Sugier, J., Walkowiak, T., Kacprzyk, J. (eds) Dependable Computer Systems and Networks. DepCoS-RELCOMEX 2023. Lecture Notes in Networks and Systems, vol 737. Springer, Cham. https://doi.org/10.1007/978-3-031-37720-4_23.

Identyfikatory

DOI

10.24425/ijet.2024.149556