More applications

Abstract We now sketch more applications of parallel algorithms for matching problems. We show that owing to the existence of RNC-algorithms for maximum matchings there exist RNC-algorithms for the following problems: bandwidth approximation, superstring approximation, cycle cover, approximate Metric TSP, unary Chinese postman problem, two-processor scheduling and the approximate Steiner tree problem. Consider the following problem. A postman is supposed to deliver the mail with in his part of the city. He starts at a post office and has to walk along each street at least once. Finally he has to return to the post office. We model the street graph as an undirected graph. For simplicity assume that each street has the same length (the unary version). Assume the graph is connected. We want to find the postman’s route which minimizes the length of the route. Observe that some streets have to be traversed more than once, unless the graph is Eulerian. We call this problem the unary postman problem.