Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More

Connectivity Maintenance of a Set of Agents through MST-based Algorithm

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Cézanne Alves, Warley Gramacho Da Silva, Rafael Lima De Carvalho

Cézanne Alves, Warley Gramacho Da Silva and Rafael Lima De Carvalho. Connectivity Maintenance of a Set of Agents through MST-based Algorithm. International Journal of Computer Applications 166(11):18-23, May 2017. BibTeX

	author = {Cézanne Alves and Warley Gramacho Da Silva and Rafael Lima De Carvalho},
	title = {Connectivity Maintenance of a Set of Agents through MST-based Algorithm},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2017},
	volume = {166},
	number = {11},
	month = {May},
	year = {2017},
	issn = {0975-8887},
	pages = {18-23},
	numpages = {6},
	url = {},
	doi = {10.5120/ijca2017914149},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}


In this paper, it is proposed a solution to the problem of positioning a set of agents that play the role of pursing a set of moving targets, while the global connectivity among such agents is maintained throughout positioning a second set of relay agents. The role of the agents consists of organizing themselves in order to allow the underlying network to stretch at its maximum (maximizing the action of pursuers), while ensuring the connectivity. In order to do that, this work proposes a positioning algorithm that uses the Minimum Spanning Tree (MST) in a way that maximizes the mobility of the nodes while deciding on the position of relays and pursuers. The approach is validated through experimental simulations using a set of behaviors to some deployed targets showing the feasibility of the proposed solution.


  1. Tekdas, O., Kumar, Y., Isler, V. et al. 2012. Building a Communication Bridge with Mobile Hubs. In IEEE T. Automation Science and Engineering v. 9, n. 1, pp. 171–176.
  2. Tekdas, O., et al. 2010. Maintaining connectivity in environments with obstacles.” In: IEEE ICRA, pp. 1952–1957.
  3. Kim, Y., Mesbahi, M. 2006. On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian, IEEE Transactions on Automatic Control, v. 51, n. 1, pp. 116–120.
  4. Godsil, C., Royle, G. 2001. Algebraic Graph Theory, v. 207, Graduate Texts in Mathematics. Volume 207 of Graduate Texts in Mathematics. Springer.
  5. De Gennaro, M., Jadbabaie, A. 2006. Decentralized Control of Connectivity for Multi-Agent Systems. In: 45th IEEE Conference on Decision and Control, pp. 3628–3633.
  6. Thunberg, J., Ogren, P. 2011. A Mixed Integer Linear Programming approach to pursuit evasion problems with optional connectivity constraints, Autonomous Robots, v. 31, n. 4, pp. 333–343.
  7. Tillet, J., Rao, T. M., Sahin, F. 2005. Darwinian Particle Swarm Optimization. In: 2nd Indian International Conference on Artificial Intelligence, pp. 1474–1487
  8. Couceiro, M., Rocha, R., and Ferreira, N. 2011. A novel multi-robot exploration approach based on Particle Swarm Optimization algorithms. In IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 327.
  9. KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, JSTOR, v. 7, n. 1, pp. 48-50
  10. Carvalho, R. L. d. 2016. Multitarget Tracking System with Connectivity Constraints. Doctoral Thesis. Federal University of Rio de Janeiro, COPPE
  11. Kuhn, H. W., Yaw, B. 1955. The Hungarian method for the assignment problem, Naval Res. Logist. Quart, pp. 83-97.


Connectivity Problem, Pursuer-evasion, Minimum Spanning Tree, Dynamic positioning problem.