๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Postman tour on a graph with precedence relation on arcs

โœ Scribed by Moshe Dror; Helman Stern; Pierre Trudeau

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
557 KB
Volume
17
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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(NS), 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.

'Throughout this paper we use terms defined in Berge [2].

๐Ÿ“œ SIMILAR VOLUMES

On a Class of Polynomials and Its Relati
On a Class of Polynomials and Its Relation with the Spectra and Diameters of Graphs
โœ M.A. Fiol; E. Garriga; J.L.A. Yebra ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 602 KB

Let \* 1 >\* 2 > } } } >\* d be points on the real line. For every k=1, 2, ..., d, the k-alternating polynomial P k is the polynomial of degree k and norm Because of this optimality property, these polynomials may be thought of as the discrete version of the Chebychev polynomials T k and, for parti