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

作　　者：Su-juan ZHENG Xiu-ming YU Li-qing CAO 

机构地区：[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

出　　处：《Water Science and Engineering》2009年第2期98-104,共7页水科学与水工程（英文版）

摘　　要：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.

关 键 词：graph theory maximal efficiency assignment problem minimal weighted k-matching algorithm intercept graph even alternating path water piping repair 

分 类 号：O224[理学—运筹学与控制论] S688.4[理学—数学]