### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2006) *Randomized vs. deterministic distance query strategies for point location on the line*.

** BibTeX **

@article{

Damaschke2006,

author={Damaschke, Peter},

title={Randomized vs. deterministic distance query strategies for point location on the line},

journal={Discrete Applied Mathematics},

issn={0166-218X},

volume={154},

issue={3},

pages={478-484},

abstract={Suppose that n points are located at n mutually distinct
but unknown positions on the line, and we can measure their pairwise distances. How many measurements are needed to determine their relative positions uniquely? The problem
is motivated by DNA mapping techniques based on pairwise distance measures. It is also interesting for its own and surprisingly deep. Continuing our earlier work on this problem, we give a simple randomized two-round strategy
that needs, with high probability, only (1+o(1))n measurements. We show that deterministic strategies cannot manage the task in two rounds with (1+o(1))n measurements
in the worst case. We improve an earlier deterministic
bound to roughly 4n/3 measurements.},

year={2006},

keywords={learning by queries, randomized strategy, graph rigidity, DNA mapping},

}

** RefWorks **

RT Journal Article

SR Print

ID 17897

A1 Damaschke, Peter

T1 Randomized vs. deterministic distance query strategies for point location on the line

YR 2006

JF Discrete Applied Mathematics

SN 0166-218X

VO 154

IS 3

SP 478

OP 484

AB Suppose that n points are located at n mutually distinct
but unknown positions on the line, and we can measure their pairwise distances. How many measurements are needed to determine their relative positions uniquely? The problem
is motivated by DNA mapping techniques based on pairwise distance measures. It is also interesting for its own and surprisingly deep. Continuing our earlier work on this problem, we give a simple randomized two-round strategy
that needs, with high probability, only (1+o(1))n measurements. We show that deterministic strategies cannot manage the task in two rounds with (1+o(1))n measurements
in the worst case. We improve an earlier deterministic
bound to roughly 4n/3 measurements.

LA eng

DO 10.1016/j.dam.2005.07.014

OL 30