Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40723
Title: The point placement problem on a line improved bounds for pairwise distance queries
Authors: Chin, F.Y.L.
Leung, H.C.M.
Sung, W.K. 
Yiu, S.M.
Issue Date: 2007
Source: 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.

Page view(s)

33
checked on Dec 16, 2017

Google ScholarTM

Check


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