an instance of guan s route inspection problem (black edges , weights) , optimal solution (doubling red edges produce eulerian multigraph)
guan known formulating route inspection problem. problem generalization of euler tour problem, in input edge-weighted graph , goal find closed walk of minimum total weight visits every graph edge @ least once. applications include transportation planning problems such planning routes fleet of snowplows plow streets of city, in minimum total time.
guan worked lecturer @ shandong normal university during great leap forward of 1958–1960, during chinese mathematicians encouraged work on practical problems. published work on route inspection problem in 1960, , paper translated english in 1962. attracted attention of jack edmonds, gave problem alternative name, chinese postman problem , in honor of guan, , proved problem can solved optimally in polynomial time.
one of guan s later contributions prove that, in contrast, windy postman problem np-complete; generalized version of route inspection problem in cost of traversing edge depends on direction in traversed.
Comments
Post a Comment