{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T06:28:40Z","timestamp":1750746520295,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SERB Govt of India","award":["EMR\/2016\/005977"],"award-info":[{"award-number":["EMR\/2016\/005977"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            In this article, we consider the problem of droplet routing for Microelectrode-Dot-Array (MEDA) biochips. MEDA biochips today provide a host of useful features for droplet movement by making it possible to manoeuvre droplets at a much finer granularity and with significantly increased flexibility. More precisely, MEDA biochips support more degrees of freedom in navigation and volumetric manipulation such as diagonal movement, droplet reshaping, and fractional-level split-and-merge. This helps improve routing of droplets on microfluidic grids\u2014in particular, when the space available on the grid is limited or blocked by obstacles. In this work, we discuss how these improved capabilities can be utilized in the realization of the desired routes on those biochips. To this end, we introduce a routing method that utilizes satisfiability solvers and guarantees the generation of optimal solutions, considering the set of MEDA operations we model. This significantly improves the state of the art, since previously proposed solutions either (1)\u00a0relied on heuristics and, hence, were not able to guarantee the optimum or (2)\u00a0only considered a subset of the MEDA features. The solution proposed in this work includes a formulation of\n            <jats:italic>all<\/jats:italic>\n            MEDA features, which, as illustrated by examples, allows for the determination of routing solutions with smaller completion times. Experimental evaluations confirm these findings.\n          <\/jats:p>","DOI":"10.1145\/3365993","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T14:07:24Z","timestamp":1575554844000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Harnessing the Granularity of Micro-Electrode-Dot-Array Architectures for Optimizing Droplet Routing in Biochips"],"prefix":"10.1145","volume":"25","author":[{"given":"Pushpita","family":"Roy","sequence":"first","affiliation":[{"name":"Calcutta University 8 Indian Statistical Institute Kolkata, Kolkata, West Bengal, India"}]},{"given":"Ansuman","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute Kolkata, Kolkata, West Bengal, India"}]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, West Bengal, Austria"}]},{"given":"Bhargab B.","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India"}]}],"member":"320","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2018. Java Development Tool Kit. Retrieved from https:\/\/www.oracle.com\/technetwork\/java\/javase\/downloads\/index.html.  2018. Java Development Tool Kit. Retrieved from https:\/\/www.oracle.com\/technetwork\/java\/javase\/downloads\/index.html."},{"key":"e_1_2_2_2_1","unstructured":"2018. Y2 the Yices tool. Retrieved from http:\/\/yices.csl.sri.com\/.  2018. Y2 the Yices tool. Retrieved from http:\/\/yices.csl.sri.com\/."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/DTIP.2015.7161024"},{"volume-title":"Proceedings of the Annual Conference on VLSI Design. 504--509","author":"Bhattacharjee Sukanta","key":"e_1_2_2_4_1"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2009.2038976"},{"volume-title":"Digital Microfluidic Biochips\u2014Synthesis, Testing, and Reconfiguration Techniques","author":"Chakrabarty Krishnendu","key":"e_1_2_2_6_1"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13206-011-5408-5"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2003282"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmat2022"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2014.6742895"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2010.5654199"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792354.1792438"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2017.7858407"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2840819.2840941"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2014.7001383"},{"volume-title":"Exact Design of Digital Microfluidic Biochips","author":"Keszocze Oliver","key":"e_1_2_2_16_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-90936-3"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593135"},{"volume-title":"Proceedings of the 2015 IEEE Asian Solid-State Circuits Conference (A-SSCC\u201915)","year":"2015","author":"Yi-Tse Lai Kelvin","key":"e_1_2_2_18_1"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-014-0939-3"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898028"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3201607.3201618"},{"key":"e_1_2_2_22_1","first-page":"37","article-title":"Flexible droplet routing in active matrix--based digital microfluidic biochips","volume":"23","author":"Lu Guan-Ruei","year":"2018","journal-title":"ACM Trans. Des. Autom. Electr. Syst."},{"key":"e_1_2_2_23_1","first-page":"870","article-title":"Single-cell analysis and sorting using droplet-based microfluidics","volume":"8","author":"Mazutis Linas","year":"2013","journal-title":"Nature"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrd3799"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature13118"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1039\/b817915h"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1039\/b814922d"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065797"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference (DATE\u201906)","year":"2006","author":"Su Fei","key":"e_1_2_2_29_1"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-nbt.2011.0018"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-nbt.2012.0043"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDAT.2015.2455344"},{"volume-title":"Proceedings of the ACM\/EDAC\/IEEE Design Automation Conference (DAC\u201907)","year":"2007","author":"Xu Tao","key":"e_1_2_2_33_1"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429461"},{"key":"e_1_2_2_35_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\/3365993","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365993","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:07Z","timestamp":1750268947000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3365993"],"URL":"https:\/\/doi.org\/10.1145\/3365993","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}