On the windy postman problem on Eulerian graphs

DOI10.1007/BF01587080MaRDI QIDQ1119487zbMATH OpenOpenAlexFDO

Authors 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 graphsminimum cost orientation closed walkpolynomial algorithmundirected connected weighted graphwindy postman problem

Mathematics Subject Classification ID

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

Review text

Given an undirected connected weighted graph G, the windy postman problem is to find a minimum cost orientation closed walk in G containing each edge at least once. The author presents a polynomial algorithm for the problem with Eulerian graphs. An approximation algorithm is given for general graphs with solution at most twice the optimum.

Recommendations

• The windy postman problem on series-parallel graphs
• On the windy postman problem
• Series-parallel graphs are windy postman perfect
• Algorithms for the windy postman problem
• Finding postal carrier walk paths in mixed graphs

Cites work

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

Cited in

(23)

• A cutting plane algorithm for the windy postman problem
• Algorithms for the windy postman problem
• Solvable cases of the \(k\)-person Chinese postman problem
• Routing problems: A bibliography
• Postman problems on series-parallel mixed graphs
• OAR lib: an open source arc routing library
• New heuristic algorithms for the windy rural postman problem
• New results on the windy postman problem
• Series-parallel graphs are windy postman perfect
• Recent results on arc routing problems: an annotated bibliography
• Approximation algorithms for the single robot line coverage problem
• The windy postman problem on series-parallel graphs
• scientific article; zbMATH DE number 1833401 (Why is no real title available?)
• scientific article; zbMATH DE number 857648 (Why is no real title available?)
• A branch-and-price algorithm for the windy rural postman problem
• Plowing with precedence in polynomial time
• The single robot line coverage problem: Theory, algorithms, and experiments
• Time-dependent windy rural postman problem: mathematical formulation and adaptive metaheuristic
• On the windy k-traveling salesman problem
• Minimum cost nowhere-zero flows and cut-balanced orientations
• On the windy postman problem
• Lower bounds and heuristics for the windy rural postman problem
• A metaheuristic for the min-max windy rural postman problem with K vehicles

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

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