1999/01/01 by Balaji Raghavachari, Jeyakesavan Veerasamy · 3 citations
Engineering · Computer Science · #Vehicle Routing Optimization Methods #Advanced Graph Theory Research #Data Management and Algorithms
paper · doi:10.1137/s0895480197331454
openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
The mixed postman problem, a generalization of the Chinese postman problem, is that of finding the shortest tour that traverses each edge of a given mixed graph (a graph containing both undirected and directed edges) at least once. The problem is solvable in polynomial time either if the graph is undirected or if the graph is directed, but it is NP-hard in mixed graphs. An approximation algorithm with a performance ratio of 3/2 for the postman problem on mixed graphs is presented.