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)

Full work available at URL https://doi.org/10.1137/S0895480197331454

zbMATH Keywords

approximation algorithmsChinese postman problemgraphsmixed postman problemNP-completeness

Mathematics Subject Classification ID

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

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

(15)

• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• Approximation algorithms for solving the constrained arc routing problem in mixed graphs
• scientific article; zbMATH DE number 4018800 (Why is no real title available?)
• Recent results on arc routing problems: an annotated bibliography
• scientific article; zbMATH DE number 1187150 (Why is no real title available?)
• scientific article; zbMATH DE number 1305467 (Why is no real title available?)
• Approximation algorithm for min-max cycle cover problem on a mixed graph
• Approximation algorithms for mixed, windy, and capacitated arc routing problems
• Variants of the mixed postman problem solvable using linear programming
• On matchings, T‐joins, and arc routing in road networks
• 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
• The single robot line coverage problem: Theory, algorithms, and experiments
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• Minimum cost nowhere-zero flows and cut-balanced orientations

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)