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

**Harvard**

Damaschke, P. (2003) *Point placement on the line by distance data*.

** BibTeX **

@article{

Damaschke2003,

author={Damaschke, Peter},

title={Point placement on the line by distance data},

journal={Discrete Applied Mathematics},

issn={0166-218X},

volume={127},

issue={1},

pages={53-62},

abstract={Given partial distance information in a set of n points on the real line, we want to figure out the positions of these points, subject to translation and reflection. This type
of problem is motivated by DNA mapping. We show the following results: If we can ask arbitrary distance
queries for pairs of points then 2n-3 adaptive queries
will be optimal. Surprisingly, if the learner knows in advance that the n points have distinct locations,
8n/5 nonadaptive queries, or alternatively 3n/2 queries in
2 rounds will be sufficient. This might be further
improved, as we only have the lower bounds 4n/3 and n, respectively. The subject is related to some rigidity concept for graphs. In another version of the problem, the graph of distance measures is already given, that means, we cannot choose our distance queries at our own discretion. Here we give a simple efficient algorithm which produces a representation of all linear layouts if the given graph is chordal.},

year={2003},

keywords={DNA mapping, pairwise distances, learning by queries, rigid graphs, chordal graphs},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 1818

A1 Damaschke, Peter

T1 Point placement on the line by distance data

YR 2003

JF Discrete Applied Mathematics

SN 0166-218X

VO 127

IS 1

SP 53

OP 62

AB Given partial distance information in a set of n points on the real line, we want to figure out the positions of these points, subject to translation and reflection. This type
of problem is motivated by DNA mapping. We show the following results: If we can ask arbitrary distance
queries for pairs of points then 2n-3 adaptive queries
will be optimal. Surprisingly, if the learner knows in advance that the n points have distinct locations,
8n/5 nonadaptive queries, or alternatively 3n/2 queries in
2 rounds will be sufficient. This might be further
improved, as we only have the lower bounds 4n/3 and n, respectively. The subject is related to some rigidity concept for graphs. In another version of the problem, the graph of distance measures is already given, that means, we cannot choose our distance queries at our own discretion. Here we give a simple efficient algorithm which produces a representation of all linear layouts if the given graph is chordal.

LA eng

DO 10.1016/S0166-218X(02)00284-6

LK http://dx.doi.org/10.1016/S0166-218X(02)00284-6

OL 30