文献

J-GLOBAL ID：202202243533010139   整理番号：22A0432602

ランダム重み付きグラフにおけるスパナ:独立エッジ長【JST・京大機械翻訳】

Spanners in randomly weighted graphs: Independent edge lengths

著者 (2件)： Frieze Alan (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, United States of America) ,  Pegden Wesley (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, United States of America)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 309  ページ： 68-74  発行年： 2022年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 連結グラフG=(V,E)と長さ関数l:E→Rを与えられた場合,dv,wは頂点vと頂点wの間の最短距離を示した。t-スパンナーは,もしdv,w′がサブグラフG′=(V,E′)で最短距離を,次にdv,w′≦tdv,wをすべてのv,w∈Vに対して示すような部分集合E′⊆Eである。独立指数平均1エッジ長を有する適切な次数と拡張特性を有するグラフの大規模クラスに対して,≒12nlognエッジを使用する1スパンナーと,これが最良可能であることを示した。特に,著者らの結果はnp≫lognに対してランダムグラフGn,pに適用した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： レンチ ,  *部分グラフ
準シソーラス用語： ランダムグラフ ,  連結グラフ , 【Automatic Indexing@JST】

著者キーワード (3件)： 最短経路 ,  スパナ ,  ランダムエッジ長

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

タイトルに関連する用語 (3件)： グラフ ,  スパナ ,  エッジ