World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Finding defectives on a line by random docking and interval group tests

    https://doi.org/10.1142/S179383091750029XCited by:0 (Source: Crossref)

    Suppose that some of the n elements of a totally ordered structure is defective, and several repair robots are at our disposal. They can dock at a random element, move at unit speed or leave, and send each other signals if there is no defective between them. We show that, by using only two robots that obey simple rules, the defective can be localized in O(n) time, which is also optimal. A variation of our strategy needs three robots but has a more predictable behavior. The model is motivated by a conjectured DNA repair mechanism, and it combines group testing with geometric search.

    AMSC: 68Q25, 68W15, 97M60

    References

    • 1. H. K. Aydinian, F. Cicalese, C. Deppe and V. Lebedev, A combinatorial model of two-aided search, in SOFSEM 2016, Lecture Notes in Computer Science, Vol. 9587, eds. R. FreivaldsG. EngelsB. Catania (Springer, 2016), pp. 149–160. Google Scholar
    • 2. R. A. Baeza-Yates, J. C. Culberson and G. J. E. Rawlins, Searching in the plane, Inform. and Comput. 16 (1993) 234–252. CrossrefGoogle Scholar
    • 3. F. Cicalese and J. A. Amgarten Quitzau, 2-Stage fault tolerant interval group testing, in ISAAC 2007, Lecture Notes in Computer Science, Vol. 4835, ed. T. Tokuyama (Springer, 2007), pp. 858–868. Google Scholar
    • 4. F. Cicalese, P. Damaschke, L. Tansini and S. Werth, Overlaps help: Improved bounds for group testing with interval queries, Discrete Appl. Math. 155 (2007) 288–299. CrossrefGoogle Scholar
    • 5. F. Cicalese, P. Damaschke and U. Vaccaro, Optimal group testing algorithms with interval queries and their application to splice site detection, Int. J. Bioinf. Res. Appl. 1 (2005) 363–388. CrossrefGoogle Scholar
    • 6. D. Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, Series on Applied Mathematics, Vol. 3 (World Scientific, 2000). Google Scholar
    • 7. M. A. Grodick, N. B. Muren and J. K. Barton, DNA charge transport within the cell, Biochemistry 54 (2015) 962–973. CrossrefGoogle Scholar
    • 8. M. Y. Kao, J. H. Reif and S. R. Tate, Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem, Inform. and Comput. 131 (1996) 63–79. CrossrefGoogle Scholar
    Remember to check out the Most Cited Articles!

    Be inspired by these NEW Mathematics books for inspirations & latest information in your research area!