You can view the full text of this article for free using the link below.

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

Available online: 23 Jan 2017 *

Full-text access for editors Access for subscribers Free access Comment on this article