On the windy postman problem
type: Item
instance of: scholarly article
title: On the windy postman problem
zbMATH Open document ID: 0551.90092
DOI: 10.1016/0166-218X(84)90089-1
author: Meigu Guan
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: The windy postman problem (WPP) is: find a shortest postman route in a connected undirected graph G(V,E), such that for every edge (x,y) the distance from x to y can be different from the distance from y to x. The author proves that WPP is NP-hard. Further, the WPP is restated as follows: let \(G_ 1(V,A)\) be a symmetric directed graph, where for every edge \(e=(x,y)\) in E there are two arcs \(a'=(x,y)\) and \(a''=(y,x)\) in A with a non-negative length \(\ell (a')\) and \(\ell(a'')\). The problem is to find a shortest directed closed path p in \(G_ 1\), such that for every \(e\in E\) at least a' or a'' belong to p. A polynomial bounded algorithm is given for solving WPP if the following condition Q is fulfilled: for every cycle C in G the corresponding cycles C' and C'' obtained from C with the two possible directions have the same length, i.e. \(\ell(C')=\ell(C'').\) Theorem 3 makes the procedure proving condition Q simpler. The author considers also the case when condition Q is ''nearly'' satisfied. G satisfies condition \(Q_ 1\), if for any cycle C in G and any edge \(e\in C\), \(| \ell(C')-\ell(C'')| <\ell(a')+\ell(a'').\) Theorem 5. If there exists a real number \(\epsilon\geq 0\) and a spanning tree T of G, such that (a) for every fundamental cycle \(C_ i\), \(| \ell (C'_ i)-\ell (C''_ i)| \leq \epsilon /s\) (s is the cyclomatic number of G), (b) for every edge e of G, \(\ell(a')+\ell(a'')>\epsilon\), then condition \(Q_ 1\) is satisfied. If G satisfies conditions (a) and (b) of Theorem 5, a polynomial bounded algorithm \((\bar A)\) is given for solving WPP approximately. Theorem 6. Let \(p_ 1\) be the shortest postman route of the WPP on G, and p be the postman route obtained by algorithm \(\bar A.\) Then \(| \ell (p_ 1)\)-\(\ell (p)| <s\epsilon\) (s and \(\epsilon\) are meant as in Theorem 5).
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3878708
zbMATH Keywords: chinese postman
zbMATH Keywords: NP-hardness
zbMATH Keywords: windy postman problem
zbMATH Keywords: connected undirected graph
zbMATH Keywords: polynomial bounded algorithm
Wikidata QID: Q55968052
MaRDI profile type: Publication
cites work: The Chinese Postman Problem for Mixed Networks
cites work: On the complexity of edge traversing
cites work: Matching, Euler tours and the Chinese postman
DBLP publication ID: journals/dam/Guan84
Recommended article: New results on the windy postman problem
Recommended article: Algorithms for the windy postman problem
Recommended article: On the windy postman problem on Eulerian graphs
Recommended article: The windy rural postman problem with a time-dependent zigzag option
Recommended article: A cutting plane algorithm for the windy postman problem
Recommended article: Q3576681
Recommended article: Plowing with precedence: a variant of the windy postman problem
Recommended article: Lower bounds and heuristics for the windy rural postman problem
Recommended article: New heuristic algorithms for the windy rural postman problem
description: scientific article; zbMATH DE number 3878708