文献

J-GLOBAL ID：202002220239355478   整理番号：20A0078958

有界空間における幾何グラフの列挙による横断【JST・京大機械翻訳】

Traversal with Enumeration of Geometric Graphs in Bounded Space

著者 (3件)： KHAKABIMAMAGHANI SAHAND (Department of Computer Science, Simon Fraser University, 8888 University Drive, Burnaby, BC V5A 1S6, Canada) ,  MASJOODY MASOOD (Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC V5A 1S6, Canada) ,  STACHO LADISLAV (Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC V5A 1S6, Canada)
資料名： Journal of Interconnection Networks  (Journal of Interconnection Networks)
巻： 19  号： 4  ページ： 1950008  発行年： 2019年 
JST資料番号： W3746A  ISSN： 0219-2659  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 本論文では,すべての頂点を訪問し,頂点とエッジを正確に報告する幾何学的グラフを横断するためのアルゴリズムを提供した。これを達成するために,与えられた幾何学的グラフGと整数格子を結合し,結果として生じる仮想グラフが顔経路選定に基づく既知のアルゴリズムを用いて横断できるように,グラフとして見られる。仮想頂点とエッジを持つ問題を克服するために,O(klog k)メモリを用いて平面に描かれたグラフ直線に頂点のk次近傍を訪問するアルゴリズムを開発した。幾何学的グラフの横断を完全にするために必要なメモリは,次に,ユークリッド距離が1より大きく,[数式:原文を参照]よりも小さいGの異なる頂点間の最大グラフ距離に依存することが分かった。Copyright 2020 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *幾何学 ,  記憶装置 ,  経路選定 ,  アルゴリズム
準シソーラス用語： Euclid距離 , 【Automatic Indexing@JST】

著者キーワード (4件)： グラフアルゴリズム ,  横断 ,  幾何グラフ ,  準平面細分化

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 有界 ,  幾何 ,  グラフ