2011年4月15日
Reconstructing sets from distances given by graphs (コンピュテーション)
電子情報通信学会技術研究報告. COMP, コンピュテーション
- ,
- ,
- 巻
- 111
- 号
- 20
- 開始ページ
- 49
- 終了ページ
- 54
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- 一般社団法人電子情報通信学会
Given n points in some Euclidean space, (^n_2) pairwise distances among the points can be easily calculated. On the other hand, it is not always possible to reconstruct a point set up to motion uniquely from a multiset of (^n_2) distances, and the computational complexity for the reconstruction is not known even if it uniquely exists. Therefore, it is a natural question to ask how much additional information is required for designing an efficient reconstruction algorithm. It becomes trivial if we know which distance corresponds to which pair of points; that is, we have a distance matrix instead of a multiset of distances. Our interest is that "what if we have a partial distance matrix?" Thus, we consider the case where partial information about the distance matrix is given: Precisely, we are given an weighted graph G=(V,E) and find an embedding of V into an Euclidean space such that the weight w(e) of each edge e gives the Euclidean distance between embedded points. Unfortunately, this problem is known to be strongly NP-hard for any Euclidean space R^d in general. In this paper, we discuss complexity of the problem for important families of graphs. We first present a polynomial-time algorithm to embed chordal graphs into R^d for any positive integer d. Then, we prove that although embedding cycles in a line is NP-hard, it becomes easy in higher-dimensions. We also give a polynomial-time algorithm to find a point set on a line from distance information given as a graph with a small connected dominating set.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110008689191
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN10013152
- URL
- http://id.ndl.go.jp/bib/11069874
- ID情報
-
- ISSN : 0913-5685
- CiNii Articles ID : 110008689191
- CiNii Books ID : AN10013152