Please use this identifier to cite or link to this item:
|Title:||The point placement problem on a line improved bounds for pairwise distance queries||Authors:||Chin, F.Y.L.
|Issue Date:||2007||Citation:||Chin, 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.||Abstract:||In 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.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/40723||ISBN:||9783540741251||ISSN:||03029743|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Apr 19, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.