文献

J-GLOBAL ID：202202248579280507   整理番号：22A0794534

メディアングラフにおけるメディアンと線形時間における立方体複合体【JST・京大機械翻訳】

Medians in median graphs and their cube complexes in linear time

著者 (4件)： Beneteau Laurine (Laboratoire d’Informatique et Systemes, Aix-Marseille Universite and CNRS, France) ,  Chalopin Jeremie (Laboratoire d’Informatique et Systemes, Aix-Marseille Universite and CNRS, France) ,  Chepoi Victor (Laboratoire d’Informatique et Systemes, Aix-Marseille Universite and CNRS, France) ,  Vaxes Yann (Laboratoire d’Informatique et Systemes, Aix-Marseille Universite and CNRS, France)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 126  ページ： 80-105  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGの頂点Pの集合の中央値は,xからPのすべての頂点までの距離の合計を最小化するGのすべての頂点xの集合である。本論文では,中央値グラフにおける中央値を計算するための線形時間アルゴリズムを提案した。また,関連するl1-キューブ錯体における中央値を計算するための線形時間アルゴリズムも示した。提案アルゴリズムは,メディアングラフにおける中央値の大多数ルールキャラクタリゼーションと,Lexicograph Breadth First Search(LexBFS)によるエッジの並列クラス(Θクラス)の高速計算に基づいている。中央値グラフの頂点のLexBFS順序付けは,次の下降旅行者特性を満たすことを示した:任意の2つの隣接頂点の親も隣接している。Θクラスの高速計算を用いて,線形時間におけるWiener指数(全距離)と最適二次時間における距離行列も計算した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *グラフ ,  時間 ,  分類 ,  距離 ,  *複合体 ,  線形性 ,  頂点 ,  高速計算
準シソーラス用語： 距離行列 ,  Wienerインデックス ,  旅行者 ,  順序づけ ,  線形時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (6件)： メディアングラフ ,  CAT(0)キューブ複合体 ,  イベント構造 ,  メディアン問題 ,  線形時間アルゴリズム ,  LexBFS

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

タイトルに関連する用語 (4件)： メディアン ,  線形 ,  立方体 ,  複合体