WEKO3
アイテム
Linear-space algorithms for distance preserving embedding
https://doi.org/10.24517/00062794
https://doi.org/10.24517/0006279462c7d9dd-f2be-4fd0-b951-7618b6a9626f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-ASANO-T-185.pdf (138.9 kB)
|
.png)
|
| アイテムタイプ | 学術雑誌論文 / Journal Article(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-07-05 | |||||||
| タイトル | ||||||||
| タイトル | Linear-space algorithms for distance preserving embedding | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| ID登録 | ||||||||
| ID登録 | 10.24517/00062794 | |||||||
| ID登録タイプ | JaLC | |||||||
| 著者 |
Asano, Tetsuo
× Asano, Tetsuo× Bose, Prosenjit× Carmi, Paz× Maheshwari, Anil× Shu, Chang× Smid, Michiel H. M.× Wuhrer, Stefanie |
|||||||
| 著者別表示 |
浅野, 哲夫
× 浅野, 哲夫
|
|||||||
| 提供者所属 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 金沢大学 | |||||||
| 書誌情報 |
CCCG 2007 - 19th Canadian Conference on Computational Geometry p. 185-188, 発行日 2007 |
|||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if distance constraints are given as a full matrix, then principal coordinate analysis can solve it in polynomial time. A serious disadvantage is its quadratic space requirement. In this paper we develop linear-space algorithms for this problem. A key idea is to partition a set of n objects into disjoint subsets (clusters) of size O(√n) such that the minimum inter cluster distance is maximized among all possible such partitions. | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | CCCG2007 The 19th Canadian Conference on Computational Geometry, August 20-22, 2007 | |||||||
| 権利 | ||||||||
| 権利情報 | Copyright © CCCG2007 The 19th Canadian Conference on Computational Geometry | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | https://2007.cccg.ca/ | |||||||
| 関連名称 | https://2007.cccg.ca/ | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | http://cccg.ca/proceedings/2007/ | |||||||
| 関連名称 | http://cccg.ca/proceedings/2007/ | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | http://cccg.ca/proceedings/2007/08a3.pdf | |||||||
| 関連名称 | http://cccg.ca/proceedings/2007/08a3.pdf | |||||||
