Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.


Conditions for Unique Graph Realizations

Bruce Hendrickson

SIAM Journal on Computing
DOI: 10.1137/0221008 (Computer Science)
Licence : non indiquée (tous droits réservés)

Résumé : The graph realization problem is that of computing the relative locations of a set of vertices placed in Euclidean space, relying only upon some set of inter-vertex distance measurements. This paper is concerned with the closely related problem of determining whether or not a graph has a unique realization. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If one assumes the vertex locations are unrelated, then the uniqueness question can be approached from a purely graph theoretic angle that ignores edge lengths. This paper identifies three necessary graph theoretic conditions for a graph to have a unique realization in any dimension. Efficient sequential and NC algorithms are presented for each condition, although these algorithms have very different flavors in different dimensions.

Publié le 01 Fév. 1992