On the windy postman problem

DOI10.1016/0166-218X(84)90089-1zbMath0551.90092WikidataQ55968052 ScholiaQ55968052MaRDI QIDQ800837

Meigu Guan

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hardnesswindy postman problemchinese postmanconnected undirected graphpolynomial bounded algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Related Items (17)

Algorithms for the windy postman problem ⋮ Solvable cases of the \(k\)-person Chinese postman problem ⋮ Lower bounds and heuristics for the windy rural postman problem ⋮ New heuristic algorithms for the windy rural postman problem ⋮ Tight bounds on the spectral radius of asymmetric nonnegative matrices ⋮ Routing problems: A bibliography ⋮ On the windy postman problem on Eulerian graphs ⋮ Postman problems on series-parallel mixed graphs ⋮ Plowing with precedence in polynomial time ⋮ Approximation Algorithms for a Mixed Postman Problem with Restrictions on the Arcs ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ New results on the windy postman problem ⋮ A cutting plane algorithm for the windy postman problem ⋮ Series-parallel graphs are windy postman perfect ⋮ Solution of real-world postman problems ⋮ Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems ⋮ Uncertain multi-objective Chinese postman problem

Cites Work

• The Chinese Postman Problem for Mixed Networks
• On the complexity of edge traversing
• Matching, Euler tours and the Chinese postman

This page was built for publication: On the windy postman problem