Efficient spanning-tree-based test pattern generation for Programmable Microfluidic Devices

Microfluidic biochips are revolutionizing the traditional biochemical experiment flow with their high execution efficiency and miniaturized fluid manipulation. To improve the flexibility of such chips, Programmable Microfluidic Devices (PMDs) have been introduced, with valves and channels built as a regular array. To take advantage of this new architecture, design automation methods have started to appear, but an efficient test generation algorithm is still unavailable. In this paper, we propose to generate test patterns based on spanning trees for this architecture. Compared with previous work, the proposed method is around 100 times faster, while the number of test patterns is still comparable.