On the windy postman problem

DOI10.1016/0166-218X(84)90089-1MaRDI QIDQ800837zbMATH OpenDBLPWikidataFDO

Authors 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)

Recommendations

• New results on the windy postman problem
• Algorithms for the windy postman problem
• On the windy postman problem on Eulerian graphs
• The windy rural postman problem with a time-dependent zigzag option
• A cutting plane algorithm for the windy postman problem
• The windy postman problem on series-parallel graphs
• Plowing with precedence: a variant of the windy postman problem
• Lower bounds and heuristics for the windy rural postman problem
• New heuristic algorithms for the windy rural postman problem

Cites work

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

Cited in

(20)

• Solution of real-world postman problems
• The windy postman problem on series-parallel graphs
• scientific article; zbMATH DE number 1833401 (Why is no real title available?)
• New heuristic algorithms for the windy rural postman problem
• Tight bounds on the spectral radius of asymmetric nonnegative matrices
• Solvable cases of the \(k\)-person Chinese postman problem
• Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems
• The single robot line coverage problem: Theory, algorithms, and experiments
• scientific article; zbMATH DE number 4185647 (Why is no real title available?)
• Routing problems: A bibliography
• Uncertain multi-objective Chinese postman problem
• Plowing with precedence in polynomial time
• Postman problems on series-parallel mixed graphs
• Lower bounds and heuristics for the windy rural postman problem
• Series-parallel graphs are windy postman perfect
• On the windy postman problem on Eulerian graphs
• A cutting plane algorithm for the windy postman problem
• New results on the windy postman problem
• Algorithms for the windy postman problem
• Approximation algorithms for a mixed postman problem with restrictions on the arcs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800837)