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

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**

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 . 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).