WEKO3
アイテム
Optimal distortion embedding of complete binary trees into lines
http://hdl.handle.net/10228/0002000074
http://hdl.handle.net/10228/0002000074057d3f97-a70a-4cfb-9ac1-265e54af3833
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347772.pdf (171 KB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-08-23 | |||||||||||||||
| 資源タイプ | ||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||
| 資源タイプ | journal article | |||||||||||||||
| タイトル | ||||||||||||||||
| タイトル | Optimal distortion embedding of complete binary trees into lines | |||||||||||||||
| 言語 | en | |||||||||||||||
| その他のタイトル | ||||||||||||||||
| その他のタイトル | Optimal Distortion Embedding of Complete Binary Trees into Lines | |||||||||||||||
| 言語 | en | |||||||||||||||
| 言語 | ||||||||||||||||
| 言語 | eng | |||||||||||||||
| 著者 |
Kumamoto, Masao
× Kumamoto, Masao
× 宮野, 英次
WEKO
6037
|
|||||||||||||||
| 抄録 | ||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||
| 内容記述 | We study the problem of embedding an unweighted complete binary tree into a line with low distortion. Very recently, Mathieu and Papamanthou (2008) [9] showed that the inorder traversal of the complete binary tree of height h gives a line embedding of distortion O(2h), and conjectured that the current lower bound of Ω(2h/h ) increases to Ω(2h), i.e., the upper bound of O(2ℎ) is best possible. In this paper, we disprove their conjecture by providing a line embedding of the complete binary tree of height h with optimal distortion Θ(2h/h). | |||||||||||||||
| 言語 | en | |||||||||||||||
| 書誌情報 |
en : Information Processing Letters 巻 112, 号 10, p. 365-370, 発行日 2012-02-09 |
|||||||||||||||
| 出版社 | ||||||||||||||||
| 出版者 | Elsevier | |||||||||||||||
| DOI | ||||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.ipl.2012.02.003 | |||||||||||||||
| ISSN | ||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||
| 収録物識別子 | 0020-0190 | |||||||||||||||
| ISSN | ||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||
| 収録物識別子 | 1872-6119 | |||||||||||||||
| 著作権関連情報 | ||||||||||||||||
| 権利情報 | Copyright (c) 2012 Elsevier B.V. All rights reserved. | |||||||||||||||
| キーワード | ||||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | line embedding | |||||||||||||||
| キーワード | ||||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | distortion | |||||||||||||||
| キーワード | ||||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | complete binary tree | |||||||||||||||
| キーワード | ||||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | optimal bound | |||||||||||||||
| 出版タイプ | ||||||||||||||||
| 出版タイプ | AM | |||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||
| 査読の有無 | ||||||||||||||||
| 値 | yes | |||||||||||||||
| 研究者情報 | ||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||
