A Constrained Chinese Postman Tour of a directed graph G(V, E) is a minimum-cost tour that traverses every edge at least once with the constraint that any two consecutive edges must not belong to a specific edge-pair subset . We first prove that this problem is NP-hard, and then we transform this problem to the Traveling Salesman Problem, so that a heuristic algorithm for the latter problem can be employed to find the approximate solution of the former problem. This new approach is then applied to generating an approximately minimum-length synchronizable test sequence that tests every transition of a protocol at least once.

Keywords: constrained Chinese postman problem, traveling salesman problem, protocol conformance testing, synchronization problem, transition graph

Received June 20, 1989; revised February 1, 1990.
Communicated by Jun S. Huang.
^*An abstract of this paper appeared in "The 2nd Workshop on Computation Theory and Discrete Mathematics," Tsing-Hua University, Hsinchu, Taiwan, R.O.C., December (1989).