Application of minimal spanning tree search algorithms to the resolution of graph problems: Case of salting and snow removal of the road network of the city of Tiaret

Abstract

The main objective of this study is to treat a primordial subject of the optimization of graph and network problems, namely the problem  of finding the spanning tree of minimum weight, which consists of identifying and determining the tree which connects all vertices of a  graph using a set of edges whose cost is minimal. Through this research study we address the problem of salting and snow removal from  the road network of the city of Tiaret during winter by the municipal authorities and services. Our mission is to determine a partial  road network (sub-network) from the initial road network of the town of Tiaret, which will have to be salted and cleared of snow by these  authorities and services. The application of graph theory techniques for modeling the problem, and the use of the main search  algorithms for the minimum weight spanning tree, allowed the study to propose the optimal subnetwork which contains the main roads  of the road network of the city of Tiaret, to salt and clear snow at the lowest possible cost.