On the windy postman problem on Eulerian graphs

DOI10.1007/BF01587080zbMath0671.90087OpenAlexW2026039289MaRDI QIDQ1119487

Zaw Win

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01587080

zbMATH Keywords

approximation algorithmEulerian graphspolynomial algorithmwindy postman problemminimum cost orientation closed walkundirected connected weighted graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Related Items (16)

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 ⋮ Routing problems: A bibliography ⋮ Postman problems on series-parallel mixed graphs ⋮ Plowing with precedence in polynomial time ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ New results on the windy postman problem ⋮ A branch-and-price algorithm for the windy rural postman problem ⋮ A cutting plane algorithm for the windy postman problem ⋮ Series-parallel graphs are windy postman perfect ⋮ Recent results on Arc Routing Problems: An annotated bibliography ⋮ A metaheuristic for the min-max windy rural postman problem with K vehicles ⋮ OAR lib: an open source arc routing library ⋮ Approximation Algorithms for the Single Robot Line Coverage Problem

Cites Work

• The mixed postman problem
• On the windy postman problem
• Eulerian Orientations and Circulations
• The Chinese Postman Problem for Mixed Networks
• Approximation Algorithms for Some Postman Problems
• Matching, Euler tours and the Chinese postman

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