文献

J-GLOBAL ID：202202236409518790   整理番号：22A1115466

木幅ρからの付加ツリーO(ρlogn)スパナ【JST・京大機械翻訳】

Additive tree O(ρlogn)-spanners from tree breadth ρ

著者 (2件)： Bendele Oliver (Institute of Optimization and Operations Research, Ulm University, Germany) ,  Rautenbach Dieter (Institute of Optimization and Operations Research, Ulm University, Germany)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 914  ページ： 39-46  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 連結グラフGの木幅tb(G)は,Gが,その袋が,ほとんどρで半径を持つツリー分解を持つような最小非負整数ρである。著者らは,次数nとサイズmの連結グラフGを与えて,1つはGの付加的ツリーO(tb(G)logn)-スパンナーを時間O(mlogn)で構築することができ,それは,Gの2頂点uとvごとにdT(u,v)≦dG(u,v)+O(tb(G)logn)であるGのスパニングサブツリーTである。これは,DraganとKohler(2014)の以前の結果を改善し,同じ順序の乗法的誤差と,O(logn)ツリーの収集による同じ加法誤差を達成したDraganとAbu-Ata(2014)を得た。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： グラフ ,  時間 ,  レンチ ,  *乗算 ,  加算 ,  整数 ,  頂点
準シソーラス用語： *木幅 ,  連結グラフ , 【Automatic Indexing@JST】

著者キーワード (4件)： 加成木スパナ ,  乗法的ツリースパナ ,  木幅 ,  ツリー長

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

タイトルに関連する用語 (2件)： 木幅 ,  スパナ