ISSN:
1436-4646
Keywords:
Windy postman problem
;
Eulerian graphs
;
polynomial algorithms
;
integer polyhedra
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The Windy Postman Problem (WPP) is defined as follows: Given an undirected connected graphG = (V, E) and costsc ij andc ji for each edgeij ∈E (wherec ij is the cost of traversing edgeij fromi toj), find a windy postman tour of minimum cost. Here, by a windy postman tour, we mean a closed directed walk which is an orientation of a closed walk inG containing each edge ofE at least once. We show in this paper that the WPP can be solved in polynomial time for Eulerian graphs, and we give a complete description of the windy postman polyhedron for this class of graphs. Based on the solvability of the WPP on Eulerian graphs, we design an approximation algorithm for the problem on general graphs and show that the value of the solution found by this algorithm is at most twice the optimum. A polynomial time algorithm and a complete description of the corresponding polytope for the minimum cost Eulerian orientation problem are also presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01587080
Permalink
