File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-540-74126-8_35
- Scopus: eid_2-s2.0-37249023662
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: The point placement problem on a line improved bounds for pairwise distance queries
Title | The point placement problem on a line improved bounds for pairwise distance queries |
---|---|
Authors | |
Issue Date | 2007 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 7th International Workshop on Algorithms in Bioinformatics (WABI 2007), PhiIadelphia, PA., 8-9 September 2007. In Lecture Notes In Computer Science, 2007, v. 4645, p. 372-382 How to Cite? |
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. |
Description | This research is supported by the RGC grant HKU7119/05E. |
Persistent Identifier | http://hdl.handle.net/10722/93450 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Leung, HCM | en_HK |
dc.contributor.author | Sung, WK | en_HK |
dc.contributor.author | Yiu, SM | en_HK |
dc.date.accessioned | 2010-09-25T15:01:31Z | - |
dc.date.available | 2010-09-25T15:01:31Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | The 7th International Workshop on Algorithms in Bioinformatics (WABI 2007), PhiIadelphia, PA., 8-9 September 2007. In Lecture Notes In Computer Science, 2007, v. 4645, p. 372-382 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93450 | - |
dc.description | This research is supported by the RGC grant HKU7119/05E. | - |
dc.description.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. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
dc.rights | The original publication is available at www.springerlink.com | - |
dc.title | The point placement problem on a line improved bounds for pairwise distance queries | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=4645&spage=372&epage=382&date=2007&atitle=The+point+placement+problem+on+a+line:+improved+bounds+for+pairwise+distance+queries | - |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.email | Leung, HCM:cmleung2@cs.hku.hk | en_HK |
dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.identifier.authority | Leung, HCM=rp00144 | en_HK |
dc.identifier.authority | Yiu, SM=rp00207 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-540-74126-8_35 | - |
dc.identifier.scopus | eid_2-s2.0-37249023662 | en_HK |
dc.identifier.hkuros | 137505 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-37249023662&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 4645 | en_HK |
dc.identifier.spage | 372 | en_HK |
dc.identifier.epage | 382 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.hkulrp | 161354 | - |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Leung, HCM=35233742700 | en_HK |
dc.identifier.scopusauthorid | Sung, WK=13310059700 | en_HK |
dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_HK |
dc.customcontrol.immutable | sml 151113 - merged | - |
dc.identifier.issnl | 0302-9743 | - |