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