On the complexity of design tasks for Digital Microfluidic Biochips. (August 2018)

• Record Type: Journal Article
• Authors: Keszocze, Oliver; Niemann, Philipp; Friedemann, Arved; Drechsler, Rolf
• Is Part Of: Microelectronics journal. Volume 78(2018)
• Page Start: 35
• Page End: 45
• Publication Date: 2018-08
• Subjects: Digital Microfluidic Biochips -- Routing -- Pin assignment -- Complexity; Microelectronics -- Periodicals; Microélectronique -- Périodiques; Microelectronics; Electronic journals; Journals - contents and abstracts; Periodicals; 621.3805
• DOI: 10.1016/j.mejo.2018.05.013
• Languages: English
• ISSNs: 0959-8324

Abstract

Abstract: Digital Microfluidic Biochips (DMFBs) is an emerging technology aiming at the automatic processing of biological assays. Experiments are conducted by routing droplets of liquids on a grid. Determining a routing is the first step in the design process. A particular routing is carried out by actuating the cells of the DMFB grid in a certain manner. These actuations are controlled by microcontrollers having a limited number of output pins. Thus, it is usually not possible to control each cell separately, but multiple cells have to share a common control pin leading to the pin assignment problem. In recent years, a wide range of heuristic as well as exact approaches has been proposed to solve these problems. While theNP -completeness of routing and pin assignment has already been conjectured in the literature, we present the first actual proofs. Thus, the use of general-purpose approaches like SAT solvers is indeed justified. We additionally prove theNP -completeness for variants of the routing problem.