Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1137/S0895480197331454 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
postman problem,chinese postman problem,mixed graph,mixed postman problem,polynomial time,approximation algorithm,shortest tour,performance ratio,2-approximation algorithm,graphs,approximation algorithms,np completeness | Discrete mathematics,Block graph,Comparability graph,Combinatorics,Line graph,Route inspection problem,Directed graph,Mixed graph,Feedback arc set,Mathematics,Graph (abstract data type) | Journal |
Volume | Issue | ISSN |
12 | 4 | 0895-4801 |
Citations | PageRank | References |
10 | 0.60 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Balaji Raghavachari | 1 | 1001 | 77.77 |
| Jeyakesavan Veerasamy | 2 | 20 | 2.79 |