Water Science and Engineering 2009, 2(2) 98-104  DOI:   10.3882/j.issn.1674-2370.2009.02.011   ISSN: 1674-2370 CN: 32-1785/TV

Current Issue | Archive | Search                                                            [Print]   [Close]
Information and Service
This Article
Supporting info
Service and feedback
Email this article to a colleague
Add to Bookshelf
Add to Citation Manager
Cite This Article
Email Alert
graph theory
maximal efficiency assignment problem
minimal weighted k-matching algorithm
intercept graph
even alternating path
water piping repair
Su-juan ZHENG
Xiu-ming YU
Li-qing CAO
Article by
Article by
Article by

Application of k-person and k-task maximal efficiency assignment algorithm to water piping repair

Su-juan ZHENG*1;Xiu-ming YU2;Li-qing CAO3

1. College of Sciences, Hohai University, Nanjing 210098, P. R. China
2. College of Computer and Information Engineering, Hohai University, Nanjing 210098, P. R. China
3. College of Hydrology and Water Resources, Hohai University, Nanjing 210098, P. R. China


Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.

Keywords graph theory   maximal efficiency assignment problem   minimal weighted k-matching algorithm   intercept graph   even alternating path   water piping repair  
Received 2008-07-11 Revised 2009-01-05 Online:  
DOI: 10.3882/j.issn.1674-2370.2009.02.011
Corresponding Authors: Su-juan ZHENG
About author:

Similar articles
1.Huan-feng DUAN; Guo-ping YU.Spanning tree-based algorithm for hydraulic simulation of large-scale water supply networks[J]. Water Science and Engineering, 2010,3(1): 23-35

Copyright by Water Science and Engineering