{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T18:08:14Z","timestamp":1770228494289,"version":"3.49.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,2]],"date-time":"2015-12-02T00:00:00Z","timestamp":1449014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Nanotechnology Research Triangle from the Indian Statistical Institute, Kolkata"},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1135853"],"award-info":[{"award-number":["CNS-1135853"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JSPS Invitational Fellowship, Japan"},{"name":"VLSI Design Project, DIT, Goverment of West Bengal"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2015,12,2]]},"abstract":"<jats:p>A digital microfluidic biochip (DMB) is often deployed for multiplexing several assays in space and in time. The residue left by one assay may contaminate the droplets used for subsequent assays. Biochemical assays involving cell culture and those based on particle microfluidics also require sweeping of residual media from an active droplet on-chip. Thus, fluidic operations such as washing or residue removal need to be performed routinely either to clean contamination from the droplet pathways or to rinse off certain droplets on the chip. In this work, several graph-based techniques are presented for offline washing of biochips that may have either a regular geometry (e.g., a 2D array of electrodes), or an irregular geometry (e.g., an application-specific layout). The schemes can be used for total washing, that is, for cleaning the entire biochip or for selective washing of sites or pathways located sparsely on the chip. The problem of reducing the path length and washing time of the droplets is investigated with or without capacity constraints. The proposed algorithms for offline washing make use of several techniques such as graph traversal, integer linear programming (ILP) modeling, and customized heuristics based on the nature of the geometric distribution of the contamination profile. The contaminated pathways are assumed to be Manhattan or curved, and hence the techniques are applicable to the conventional field-actuated DMBs as well as to the emerging classes of light-actuated and active-matrix DMBs. These techniques will be useful in enhancing the reliability of a wide class of emerging digital microfluidic healthcare devices<\/jats:p>","DOI":"10.1145\/2798726","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Offline Washing Schemes for Residue Removal in Digital Microfluidic Biochips"],"prefix":"10.1145","volume":"21","author":[{"given":"Debasis","family":"Mitra","sequence":"first","affiliation":[{"name":"National Institute of Technology, Durgapur, India"}]},{"given":"Sarmishtha","family":"Ghoshal","sequence":"additional","affiliation":[{"name":"Indian Institute of Engineering Science and Technology, Howrah, India"}]},{"given":"Hafizur","family":"Rahaman","sequence":"additional","affiliation":[{"name":"Indian Institute of Engineering Science and Technology, Howrah, India"}]},{"given":"Krishnendu","family":"Chakrabarty","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Bhargab B.","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]}],"member":"320","published-online":{"date-parts":[[2015,12,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.01.007"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1039\/c002147d"},{"key":"e_1_2_2_3_1","unstructured":"Michel Berkelaar Kjell Eikland and Peter Notebaert. 2004. lp_solve 5.5 open source (mixed-integer) linear programming system software. http:\/\/lpsolve.sourceforge.net\/5.5\/ (Last accessed March 28 2015).  Michel Berkelaar Kjell Eikland and Peter Notebaert. 2004. lp_solve 5.5 open source (mixed-integer) linear programming system software. http:\/\/lpsolve.sourceforge.net\/5.5\/ (Last accessed March 28 2015)."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"K. Chakrabarty and F. Su. 2007. Digital Microfluidic Biochips: Synthesis Testing and Reconfiguration Techniques. CRC Press.  K. Chakrabarty and F. Su. 2007. Digital Microfluidic Biochips: Synthesis Testing and Reconfiguration Techniques. CRC Press.","DOI":"10.1201\/9781420008302"},{"key":"e_1_2_2_5_1","volume-title":"Basic Techniques of Combinatorial Theory","author":"Cohen D.","unstructured":"D. Cohen . 1979. Basic Techniques of Combinatorial Theory . Wiley , Hoboken, NJ . D. Cohen. 1979. Basic Techniques of Combinatorial Theory. Wiley, Hoboken, NJ."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.11.2.138"},{"key":"e_1_2_2_7_1","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"Deo N.","unstructured":"N. Deo . 1994. Graph Theory with Applications to Engineering and Computer Science . Prentice-Hall of India Pvt. Ltd . N. Deo. 1994. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall of India Pvt. Ltd."},{"key":"e_1_2_2_8_1","unstructured":"Dilyx. 2012. Protein solubility. http:\/\/www.dilyx.com\/index.php\/resources\/protein_solubility_basics\/.  Dilyx. 2012. Protein solubility. http:\/\/www.dilyx.com\/index.php\/resources\/protein_solubility_basics\/."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2007.8"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_2_2_12_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.859515"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380445.2380510"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"J. L. Gross and J. Yellen. 2003. Handbook of Graph Theory. CRC Press.  J. L. Gross and J. Yellen. 2003. Handbook of Graph Theory. CRC Press.","DOI":"10.1201\/9780203490204"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1039\/c2lc40273d"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2284010"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656106.2656118"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792354.1792438"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2062770"},{"key":"e_1_2_2_21_1","unstructured":"C. Jin X. Xiong P. Patra R. Zhu and J. Hu. 2014. Design and simulation of high-throughput microfluidic droplet dispenser for lab-on-a-chip applications. Excerpt from phProceedings of the COMSOL Conference. 1--7.  C. Jin X. Xiong P. Patra R. Zhu and J. Hu. 2014. Design and simulation of high-throughput microfluidic droplet dispenser for lab-on-a-chip applications. Excerpt from phProceedings of the COMSOL Conference. 1--7."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.04.001"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593135"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the IEEE Conference on Automation Science and Engineering. 678--683","author":"Koyama N.","unstructured":"N. Koyama , K. Ohara , A. Hasegawa , T. Takubo , Y. Mae , and T. Arai . 2011. Multiple cell suction and supply system for automated cell manipulation on microfluidic channel . In Proceedings of the IEEE Conference on Automation Science and Engineering. 678--683 . N. Koyama, K. Ohara, A. Hasegawa, T. Takubo, Y. Mae, and T. Arai. 2011. Multiple cell suction and supply system for automated cell manipulation on microfluidic channel. In Proceedings of the IEEE Conference on Automation Science and Engineering. 678--683."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2006.871483"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2108010"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the IEEE\/ACM Design, Automation and Test in Europe. 1239--1244","author":"Luo Y.","year":"2012","unstructured":"Y. Luo , K. Chakrabarty , and T.-Y. Ho . 2012 . A cyberphysical synthesis approach for error recovery in digital microfluidic biochips . In Proceedings of the IEEE\/ACM Design, Automation and Test in Europe. 1239--1244 . Y. Luo, K. Chakrabarty, and T.-Y. Ho. 2012. A cyberphysical synthesis approach for error recovery in digital microfluidic biochips. In Proceedings of the IEEE\/ACM Design, Automation and Test in Europe. 1239--1244."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10617-012-9083-0"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1973009.1973091"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10836-011-5239-2"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the IEEE International Conference on Automation Science & Engineering. 115--120","author":"Mitra D.","unstructured":"D. Mitra , S. Ghoshal , H. Rahaman , K. Chakrabarty , and B. B. Bhattacharya . 2012. Automated path planning for washing in digital microfluidic biochips . In Proceedings of the IEEE International Conference on Automation Science & Engineering. 115--120 . D. Mitra, S. Ghoshal, H. Rahaman, K. Chakrabarty, and B. B. Bhattacharya. 2012. Automated path planning for washing in digital microfluidic biochips. In Proceedings of the IEEE International Conference on Automation Science & Engineering. 115--120."},{"key":"e_1_2_2_32_1","first-page":"12","article-title":"Droplet actuation by electrowetting-on-dielectric (EWOD): A review","volume":"26","author":"Nelsona W. C.","year":"2012","unstructured":"W. C. Nelsona and C.-J. Kim . 2012 . Droplet actuation by electrowetting-on-dielectric (EWOD): A review . J. Adhesion Sci. Technol. 26 , 12 -- 17 (2012), 1747--1771. W. C. Nelsona and C.-J. Kim. 2012. Droplet actuation by electrowetting-on-dielectric (EWOD): A review. J. Adhesion Sci. Technol. 26, 12--17 (2012), 1747--1771.","journal-title":"J. Adhesion Sci. Technol."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1021\/ac3020627"},{"key":"e_1_2_2_34_1","unstructured":"V. K. Pamula 2012. Advanced liquid logic. Private correspondence.  V. K. Pamula 2012. Advanced liquid logic. Private correspondence."},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the IEEE International Conference on Micro Electro Mechanical Systems. 252--255","author":"Pei S. N.","unstructured":"S. N. Pei , J. K. Valley , S. L. Neale , A. Jamshidi , H.-Y. Hsu , and M. C. Wu . 2010. Light-actuated digital microfluidics for large scale, parallel manipulation of arbitrarily sized droplets . In Proceedings of the IEEE International Conference on Micro Electro Mechanical Systems. 252--255 . S. N. Pei, J. K. Valley, S. L. Neale, A. Jamshidi, H.-Y. Hsu, and M. C. Wu. 2010. Light-actuated digital microfluidics for large scale, parallel manipulation of arbitrarily sized droplets. In Proceedings of the IEEE International Conference on Micro Electro Mechanical Systems. 252--255."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1785481.1785583"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061790"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the IEEE Conference on Automation Science and Engineering. 381--386","author":"Sapuppo F.","unstructured":"F. Sapuppo , P. Anandan , and M. Bucolo . 2011. Micro-optic technology for the microfluidics feedback . In Proceedings of the IEEE Conference on Automation Science and Engineering. 381--386 . F. Sapuppo, P. Anandan, and M. Bucolo. 2011. Micro-optic technology for the microfluidics feedback. In Proceedings of the IEEE Conference on Automation Science and Engineering. 381--386."},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the International Conference on Mechatronics and Embedded Systems and Applications (MESA). 251--256","author":"Singha K.","unstructured":"K. Singha , T. Samanta , H. Rahaman , and P. Dasgupta . 2010. Method of droplet routing in digital microfluidic biochip . In Proceedings of the International Conference on Mechatronics and Embedded Systems and Applications (MESA). 251--256 . K. Singha, T. Samanta, H. Rahaman, and P. Dasgupta. 2010. Method of droplet routing in digital microfluidic biochip. In Proceedings of the International Conference on Mechatronics and Embedded Systems and Applications (MESA). 251--256."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1039\/b814922d"},{"key":"e_1_2_2_41_1","volume-title":"Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica","author":"Skiena S.","unstructured":"S. Skiena . 1990. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica . Addison-Wesley , Reading, MA . S. Skiena. 1990. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Addison-Wesley, Reading, MA."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10836-006-0554-8"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142155.1142164"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1039\/b715524g"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(83)90041-7"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593189"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1021\/ac048754"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/VTS.2009.16"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837437"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2183369"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2798726","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2798726","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:18Z","timestamp":1750223238000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2798726"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,2]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12,2]]}},"alternative-id":["10.1145\/2798726"],"URL":"https:\/\/doi.org\/10.1145\/2798726","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,2]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}