Postman tour on a graph with precedence relation on arcs
Authors:
Abstract
Since the introduction of the Chinese Postman Problem (CPP), many variations on the same theme have been developed. In this paper we examine still another variation. The arcs of the graph are partitioned and a precedence relation defined, specifying the order in which the elements of the partition have to be traversed. We first examine the conditions for a feasible solution to the problem. Next, we specify the graph properties of the precedence partition that insure a polynomial complexity solution of O(N5), where N is the number of nodes in the original graph. When the precedence relation on sets of arcs is general, we prove that the problem of finding the minimum length of feasible postman tour is NP‐complete.Keywords
This publication has 9 references indexed in Scilit:
- Pierce point minimization and optimal torch path determination in flame cuttingJournal of Manufacturing Systems, 1984
- An analysis of alternative strategies for implementing matching algorithmsNetworks, 1983
- Capacitated arc routing problemsNetworks, 1981
- Approximation Algorithms for Some Postman ProblemsJournal of the ACM, 1979
- Routing electric meter readersComputers & Operations Research, 1979
- On the complexity of edge traversingJournal of the ACM, 1976
- On general routing problemsNetworks, 1976
- A fundamental problem in vehicle routingNetworks, 1974
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973