https://scholars.lib.ntu.edu.tw/handle/123456789/118210
Title: | Bioroute: A Network-Flow Based Routing Algorithm for Digital Microfluidic Biochips | Authors: | Yuh, Ping-Hung Yang, Chia-Lin CHIA-LIN YANG |
Issue Date: | 2007 | Start page/Pages: | 752-757 | Source: | IEEE/ACM International Conference on Computer-Aided Design | Abstract: | 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, we 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. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of non-interfering nets and then adopt the network-flow approach to generate optimal global-routing paths for the nets. In detailed routing, we present the first polynomial-time algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. The experimental results show the robustness and efficiency of our algorithm. © 2007 IEEE. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/232558 http://ntur.lib.ntu.edu.tw/bitstream/246246/232558/-1/06.pdf |
DOI: | 10.1109/ICCAD.2007.4397356 | SDG/Keyword: | Bioassay; Biochips; Design; Digital arithmetic; Drop formation; Drops; Fluid mechanics; Marine biology; Microarrays; Nanofluidics; Network routing; Scheduling; Scheduling algorithms; Set theory; Biochip; Computer-aided design; Detailed routing; Digital microfluidic biochips; Droplet routing; Flow based; Global routing; International conferences; Laboratory procedures; Polynomial-time algorithms; Routing and scheduling; Routing paths; Routing problems; Routing schemes; Two stages; VLSI routing; Routing algorithms |
Appears in Collections: | 資訊工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.