Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/40723
DC FieldValue
dc.titleThe point placement problem on a line improved bounds for pairwise distance queries
dc.contributor.authorChin, F.Y.L.
dc.contributor.authorLeung, H.C.M.
dc.contributor.authorSung, W.K.
dc.contributor.authorYiu, S.M.
dc.date.accessioned2013-07-04T08:10:52Z
dc.date.available2013-07-04T08:10:52Z
dc.date.issued2007
dc.identifier.citationChin, F.Y.L.,Leung, H.C.M.,Sung, W.K.,Yiu, S.M. (2007). The point placement problem on a line improved bounds for pairwise distance queries. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4645 LNBI : 372-382. ScholarBank@NUS Repository.
dc.identifier.isbn9783540741251
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40723
dc.description.abstractIn this paper, we study the adaptive version of the point placement problem on a line, which is motivated by a DNA mapping problem. To identify the relative positions of n distinct points on a straight line, we are allowed to ask queries of pairwise distances of the points in rounds. The problem is to find the number of queries required to determine a unique solution for the positions of the points up to translation and reflection. We improved the bounds for several cases. We show that An/3 + O(√n) queries are sufficient for the case of two rounds while the best known result was 3n/2 queries. For unlimited number of rounds, the best result was 4n/3 queries. We obtain a much better result of using 5n/4 + O(√n) queries with three rounds only. We also improved the lower bound of 30n/29 to 17n/16 for the case of two rounds. © Springer-Verlag Berlin Heidelberg 2007.
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume4645 LNBI
dc.description.page372-382
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

53
checked on May 17, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.