Geodesic
More on Generalized Jewels and the Point Placement Problem
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 1, pp. 133-173.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The point placement problem is to determine the positions of a set of n distinct points, P = {p1, p2, p3, ..., pn}, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distance query corresponds to an edge in a graph, called point placement graph (ppg), whose vertex set is P. The uniqueness requirement of the placement translates to line-rigidity of the ppg. In this paper we show how to construct in 2 rounds a line-rigid point placement graph of size 4n/3 + O(1) from certain small-sized graphs called 6:6 jewels. This improves an earlier result that used cycle-graphs on 5 vertices. More significantly, we improve the lower bound on 2-round algorithms from 17n/16 to 12n/11. 
@article{JGAA_2014_18_1_a4,
     author = {Md. Shafiul Alam and Asish Mukhopadhyay},
     title = {More on {Generalized} {Jewels} and the {Point
Placement} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {133--173},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2014},
     doi = {10.7155/jgaa.00317},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00317/}
}
TY  - JOUR
AU  - Md. Shafiul Alam
AU  - Asish Mukhopadhyay
TI  - More on Generalized Jewels and the Point
Placement Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 133
EP  - 173
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00317/
DO  - 10.7155/jgaa.00317
LA  - en
ID  - JGAA_2014_18_1_a4
ER  - 
%0 Journal Article
%A Md. Shafiul Alam
%A Asish Mukhopadhyay
%T More on Generalized Jewels and the Point
Placement Problem
%J Journal of Graph Algorithms and Applications
%D 2014
%P 133-173
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00317/
%R 10.7155/jgaa.00317
%G en
%F JGAA_2014_18_1_a4
Md. Shafiul Alam; Asish Mukhopadhyay. More on Generalized Jewels and the Point
Placement Problem. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 1, pp. 133-173. doi : 10.7155/jgaa.00317. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00317/

Cité par Sources :