Title: An efficient and refined minimum spanning tree approach for large water distribution system
Authors: S.V.S. Santhi; P. Padmaja
Addresses: Department of Information Technology, GITAM Institute of Technology (GIT), GITAM University, Visakhapatnam – 530045, Andhra Pradesh, India ' Department of Information Technology, GITAM Institute of Technology (GIT), GITAM University, Visakhapatnam – 530045, Andhra Pradesh, India
Abstract: For the past several years, large graph mining applications have been used for a wide range of analyses. One such application is a water distribution system (WDS). WDSs are networked with both topological and behavioural complexity since it comprises of a large number of pipes and junctions. Therefore, it becomes highly expensive to design such large WDSs. Hence, in this paper, we suggest to construct a reduced WDS network with minimum cost by applying a minimum spanning tree (MST) approach. However, it becomes difficult to apply traditional MST algorithms to large graphs because they have a time complexity of O(N2log N). Therefore the authors propose a divide-and-conquer mechanism for finding an approximate MST. The proposed approach shows the novelty of the algorithm by reducing the time complexity to O(N1.5log N). Experimental results show that the proposed approach had performed well and fit the expected results for both synthetic and real-world data.
Keywords: graph partitioning; minimum spanning tree; water distribution networks; water supply; large graph mining; network design.
DOI: 10.1504/IJDSS.2016.081777
International Journal of Decision Support Systems, 2016 Vol.2 No.1/2/3, pp.181 - 206
Received: 16 Oct 2015
Accepted: 30 Aug 2016
Published online: 24 Jan 2017 *