| Article ID: | iaor20002815 |
| Country: | United States |
| Volume: | 12 |
| Issue: | 4 |
| Start Page Number: | 425 |
| End Page Number: | 433 |
| Publication Date: | Oct 1999 |
| Journal: | SIAM Journal on Discrete Mathematics |
| Authors: | Raghavachari Balaji, Veerasamy Jeyakesavan |
| Keywords: | graphs |
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.