{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:21:49Z","timestamp":1754108509588,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1536026"],"award-info":[{"award-number":["CCF-1536026"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>\n            We address the problem of designing micro-fluidic chips for sample preparation, which is a crucial step in many experimental processes in chemical and biological sciences. One of the objectives of sample preparation is to dilute the sample fluid, called reactant, using another fluid called buffer, to produce desired volumes of fluid with prespecified reactant concentrations. In the model we adopt, these fluids are manipulated in discrete volumes called droplets. The dilution process is represented by a\n            <jats:italic>mixing graph<\/jats:italic>\n            whose nodes represent 1-1 micro-mixers and edges represent channels for transporting fluids. In this work, we focus on designing such mixing graphs when the given sample (also referred to as the\n            <jats:italic>target<\/jats:italic>\n            ) consists of a single-droplet, and the objective is to minimize total fluid waste. Our main contribution is an efficient algorithm called RPRIS that guarantees a better provable worst-case bound on waste and significantly outperforms state-of-the-art algorithms in experimental comparison.\n          <\/jats:p>","DOI":"10.1145\/3408297","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T11:13:41Z","timestamp":1601464421000},"page":"1-22","source":"Crossref","is-referenced-by-count":1,"title":["A Waste-Efficient Algorithm\u00a0for Single-Droplet Sample Preparation on Microfluidic Chips"],"prefix":"10.1145","volume":"25","author":[{"given":"Miguel Coviello","family":"Gonzalez","sequence":"first","affiliation":[{"name":"University of California at Riverside, Riverside, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"volume-title":"Algorithms for Sample Preparation with Microfluidic Lab-on-Chip","author":"Bhattacharjee Sukanta","key":"e_1_2_1_1_1","unstructured":"Sukanta Bhattacharjee , Bhargab B. Bhattacharya , and Krishnendu Chakrabarty . 2019. Algorithms for Sample Preparation with Microfluidic Lab-on-Chip . River Publishers . Sukanta Bhattacharjee, Bhargab B. Bhattacharya, and Krishnendu Chakrabarty. 2019. Algorithms for Sample Preparation with Microfluidic Lab-on-Chip. River Publishers."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04126-1_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLDI-DAT.2013.6533817"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2014.6742894"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSI-DAT.2019.8742025"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17402-6_16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429464"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2263035"},{"volume-title":"IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 314--319","author":"Mitra Debasis","key":"e_1_2_1_9_1","unstructured":"Debasis Mitra , Sudip Roy , Krishnendu Chakrabarty , and Bhargab B. Bhattacharya . 2012. On-chip sample preparation with multiple dilutions using digital microfluidics . In IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 314--319 . Debasis Mitra, Sudip Roy, Krishnendu Chakrabarty, and Bhargab B. Bhattacharya. 2012. On-chip sample preparation with multiple dilutions using digital microfluidics. In IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 314--319."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061790"},{"key":"e_1_2_1_11_1","volume-title":"Bhattacharya","author":"Roy Sudip","year":"2015","unstructured":"Sudip Roy , Partha P. Chakrabarti , Krishnendu Chakrabarty , and Bhargab B . Bhattacharya . 2015 . Waste-aware single-target dilution of a biochemical fluid using digital microfluidic biochips. Integration, the VLSI Journal 51 (2015), 194--207. Sudip Roy, Partha P. Chakrabarti, Krishnendu Chakrabarty, and Bhargab B. Bhattacharya. 2015. Waste-aware single-target dilution of a biochemical fluid using digital microfluidic biochips. Integration, the VLSI Journal 51 (2015), 194--207."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-006-9032-6"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3408297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:39:02Z","timestamp":1750199942000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":12,"alternative-id":["10.1145\/3408297"],"URL":"https:\/\/doi.org\/10.1145\/3408297","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,9,30]]}}}