Wen-Huei Chen, Ching-Sung Lu, Jinn-Tuu Wang
and Richard-Jinjr Lee
Protocols Research Group
P.O. Box 71, Chung-Li, Taiwan, R.O.C.
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).