Series-parallel graphs are windy postman perfect. (English) Zbl 1137.05061
Summary: The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph \(G\), we consider the polyhedron \(O(G)\) induced by a linear programming relaxation of the windy postman problem. We say that \(G\) is windy postman perfect if \(O(G)\) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to \(O(G)\), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Z. Win [Contribution to routing problems. Ph.D. Thesis, University Augsburg, Germany (1987) and Math. Program., Ser. A 44, 97–112 (1989; Zbl 0671.90087)].
MSC:
| 05C75 | Structural characterization of families of graphs |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C17 | Perfect graphs |
Citations:
Zbl 0671.90087Software:
PORTAReferences:
| [1] | T. Christof, A. Löbel, —POlyhedron Representation Transformation Algorithm, December 2002, ©1997-2002 by Konrad-Zuse-Zentrum für Informationstechnik, Berlin.; T. Christof, A. Löbel, —POlyhedron Representation Transformation Algorithm, December 2002, ©1997-2002 by Konrad-Zuse-Zentrum für Informationstechnik, Berlin. |
| [2] | Duffin, R. J., Topology of series-parallel networks, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002 |
| [3] | Edmonds, J.; Johnson, E. L., Matching, Euler tours and the Chinese postman, Math. Programming, 5, 88-124 (1973) · Zbl 0281.90073 |
| [4] | C.G. Fernandes, O. Lee, Y. Wakabayashi, The minimum cycle cover and the Chinese postman problems on mixed graphs with bounded tree width, 2003. Available at \(\langle;\) http://www.ime.usp.br/\( \sim;\) yw/\( \rangle;\).; C.G. Fernandes, O. Lee, Y. Wakabayashi, The minimum cycle cover and the Chinese postman problems on mixed graphs with bounded tree width, 2003. Available at \(\langle;\) http://www.ime.usp.br/\( \sim;\) yw/\( \rangle;\). · Zbl 1168.05318 |
| [5] | Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 2, 169-197 (1981) · Zbl 0492.90056 |
| [6] | Grötschel, M.; Win, Z., A cutting plane algorithm for the windy postman problem, Math. Programming, 55 Ser. A, 3, 339-358 (1992) · Zbl 0761.90082 |
| [7] | Guan, M. G., On the windy postman problem, Discrete Appl. Math., 9, 1, 41-46 (1984) · Zbl 0551.90092 |
| [8] | Minieka, E., The Chinese postman problem for mixed networks, Management Sci., 25, 7, 643-648 (1979) · Zbl 0423.90048 |
| [9] | Z. Win, Contributions to routing problems, Ph.D. Thesis, Universität Augsburg, Germany, 1987.; Z. Win, Contributions to routing problems, Ph.D. Thesis, Universität Augsburg, Germany, 1987. · Zbl 0654.90034 |
| [10] | Win, Z., On the windy postman problem on Eulerian graphs, Math. Programming, 44 Ser. A, 1, 97-112 (1989) · Zbl 0671.90087 |
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.
