BioRoute: A Network-Flow Based Routing Algorithm for Digital Microfluidic Biochips

Due to the recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional VLSI routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction of the synthesis result. In this paper, authors present the first network-flow based routing algorithm that can concurrently route a set of non-interfering nets for the droplet routing problem on biochips.