Name
Title | ||
|---|---|---|
A Matroid-Theoretic Solution to an Assignment Problem in the Conformance Testing of Communication Protocols |
Abstract | ||
|---|---|---|
The minimum length test sequence generation method proposed in [2] for conformance testing of a protocol uses Unique Input Sequences (UIS) for state identification. This method, called the U-method, requires that the test graph, a graph derived from the protocol, be connected. This requirement also needs to be satisfied in the case of the MU-method [31], [30], which assumes that the multiple UISs are available for each state. Thus, the U-method and the MU-method may not provide minimum length test sequences in cases where the test graph is not connected. Nevertheless, these methods generate minimum length test sequences with high fault coverage whenever the test graph is connected. This raises an important problem: Does there exist an assignment of UISs to the transitions such that the resulting test graph is connected? In this paper, we formulate this problem as a maximum cardinality two matroid intersection problem and discuss an efficient algorithmic solution. We also point out the role of the work in the minimum length test sequence generation problem. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/12.844345 | IEEE Trans. Computers |
Keywords | Field | DocType |
state identification,unique input sequences,test graph,assignment problem,resulting test graph,multiple uiss,matroid intersection problem,matroid-theoretic solution,important problem,conformance testing,generation problem,communication protocols,minimum length test sequence,generation method,testing,communication,communication protocol,graph theory,matroids,algorithms,fault coverage,protocols,satisfiability,protocol | Graph theory,Discrete mathematics,Strength of a graph,Matroid intersection,Computer science,Distance-hereditary graph,Null graph,Aperiodic graph,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
49 | 4 | 0018-9340 |
Citations | PageRank | References |
3 | 0.66 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| T Ramalingom | 1 | 21 | 1.79 |
| Krishnaiyan Thulasiraman | 2 | 255 | 25.49 |
| Anindya Das | 3 | 219 | 31.78 |