On the windy postman problem on Eulerian graphs. (English) Zbl 0671.90087
Given an undirected connected weighted graph G, the windy postman problem is to find a minimum cost orientation closed walk in G containing each edge at least once. The author presents a polynomial algorithm for the problem with Eulerian graphs. An approximation algorithm is given for general graphs with solution at most twice the optimum.
Reviewer: H.T.Lau
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C05 | Linear programming |
| 90C10 | Integer programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
undirected connected weighted graph; windy postman problem; minimum cost orientation closed walk; polynomial algorithm; Eulerian graphs; approximation algorithmReferences:
| [1] | J. Edmonds and E. Johnson, ”Matching, Euler tours and the Chinese postman,”Mathematical Programming 5 (1973) 88–124. · Zbl 0281.90073 · doi:10.1007/BF01580113 |
| [2] | G.N. Frederickson, ”Approximation algorithms for some postman problems,”Journal of the Association for Computing Machinery 26 (1979) 538–554. · Zbl 0405.90076 |
| [3] | M. Guan, ”On the Windy Postman Problem,”Discrete Applied Mathematics 9 (1984) 41–46. · Zbl 0551.90092 · doi:10.1016/0166-218X(84)90089-1 |
| [4] | M. Guan and W. Pulleyblank, ”Eulerian orientations and circulations,”SIAM Journal on Algebra and Discrete Mathematics 6 (1985) 657–664. · Zbl 0576.05046 · doi:10.1137/0606065 |
| [5] | C.H. Kappauf and G.J. Koehler, ”The mixed postman problem,”Discrete Applied Mathematics 1 (1979) 89–103. · Zbl 0416.90048 · doi:10.1016/0166-218X(79)90016-7 |
| [6] | E. Minieka, ”The Chinese postman problem for mixed networks,”Management Science 25 (1979) 643–648. · Zbl 0423.90048 · doi:10.1287/mnsc.25.7.643 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
