Francisco Javier Zaragoza Martínez

The Windy Postman Problem on SeriesParallel Graphs
dmtcs:3396 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3396
The Windy Postman Problem on SeriesParallel Graphs
Authors: Francisco Javier Zaragoza Martínez ^{1}
NULL
Francisco Javier Zaragoza Martínez
1 Departamento de Sistemas [Azcapotzalco]
The windy postman problem is the NPhard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of traversal of an edge depends on the direction. Given an undirected graph $G$, we consider the polyhedron $O(G)$ induced by the linear programming relaxation of a wellknown integer programming formulation of the problem. We say that $G$ is windy postman perfect if $O(G)$ is integral. There exists a polynomialtime algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. Eulerian graphs and trees are windy postman perfect. By considering a family of polyhedra related to $O(G)$, we prove that seriesparallel graphs are windy postman perfect, therefore solving a conjecture of [Win1987a].