File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: The point placement problem on a line improved bounds for pairwise distance queries

TitleThe point placement problem on a line improved bounds for pairwise distance queries
Authors
Issue Date2007
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4645 LNBI, p. 372-382 How to Cite?
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.
Description7th International Workshop on Algorithms in Bioinformatics (WABI 2007), Philadelphia, PA, USA, 8-9 September 2007. This research is supported by the RGC grant HKU7119/05E.
Persistent Identifierhttp://hdl.handle.net/10722/93450
ISSN
2014 SCImago Journal Rankings: 0.339
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorLeung, HCMen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-25T15:01:31Z-
dc.date.available2010-09-25T15:01:31Z-
dc.date.issued2007en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4645 LNBI, p. 372-382en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93450-
dc.description7th International Workshop on Algorithms in Bioinformatics (WABI 2007), Philadelphia, PA, USA, 8-9 September 2007. This research is supported by the RGC grant HKU7119/05E.-
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.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleThe point placement problem on a line improved bounds for pairwise distance queriesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://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.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailLeung, HCM:cmleung2@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityLeung, HCM=rp00144en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-74126-8_35-
dc.identifier.scopuseid_2-s2.0-37249023662en_HK
dc.identifier.hkuros161354en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-37249023662&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4645 LNBIen_HK
dc.identifier.spage372en_HK
dc.identifier.epage382en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridLeung, HCM=35233742700en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats