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(N²log 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(N^1.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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article