Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.6 No.2, pp.149-157 (June 1990)
Constrained Chinese Postman Problem with Its
Application on Synchronizable Protocol
Test Generation*

Wen-Huei Chen, Ching-Sung Lu, Jinn-Tuu Wang
and Richard-Jinjr Lee
Protocols Research Group
Telecommunication Laboratories
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 JISE. 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).