A 3/2-Approximation Algorithm for the Mixed Postman Problem

DOI10.1137/S0895480197331454MaRDI QIDQ4699169zbMATH OpenFDO

Authors Balaji Raghavachari, Jeyakesavan Veerasamy

Publication date 23 November 1999

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graphsapproximation algorithmsChinese postman problemNP-completenessmixed postman problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Inventory, storage, reservoirs (90B05)

Recommendations

• scientific article; zbMATH DE number 1187150
• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• scientific article; zbMATH DE number 1305467
• scientific article; zbMATH DE number 3871059
• Approximation algorithms for solving the heterogeneous Chinese postman problem
• Approximation algorithms for some min-max postmen cover problems
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Approximation algorithms for some minimum postmen cover problems
• Approximation algorithms for some minimum postmen cover problems
• An approximation algorithm for solving the heterogeneous Chinese postman problem

Cited in

(13)

• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• scientific article; zbMATH DE number 1187150 (Why is no real title available?)
• Variants of the mixed postman problem solvable using linear programming
• scientific article; zbMATH DE number 4018800 (Why is no real title available?)
• Approximation algorithms for solving the constrained arc routing problem in mixed graphs
• The single robot line coverage problem: Theory, algorithms, and experiments
• On matchings, T‐joins, and arc routing in road networks
• Recent results on arc routing problems: an annotated bibliography
• Approximation algorithm for min-max cycle cover problem on a mixed graph
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• Approximation algorithms for a mixed postman problem with restrictions on the arcs

This page was built for publication: A 3/2-Approximation Algorithm for the Mixed Postman Problem

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