文献

J-GLOBAL ID：201702244616577942   整理番号：17A1240858

小さな高さを有する大規模な木のカットツリー【Powered by NICT】

The cut-tree of large trees with small heights

著者 (1件)： Berzunza Gabriel (Institut fuer Mathematik, Universitaet Zuerich, Winterthurerstrasse 190, CH-8057, Zuerich, Switzerland)
資料名： Random Structures & Algorithms  (Random Structures & Algorithms)
巻： 51  号： 3  ページ： 404-427  発行年： 2017年 
JST資料番号： W0149A  ISSN： 1042-9832  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： は他の後で均一なランダムな順序でそのエッジを切断によってサイズnの有限木を破壊する。非公式には,関連するカット樹ではこの破壊過程により生成された連結成分の家系について述べた。ユークリッド距離とある種の確率測度を与えられた間隔にGromov Prohorovトポロジーの再スケールカット木の収束のための一般的基準を提供し,根底にある樹木は,O(n)の根と高さに近い分岐点を持っている。特に,一様ランダム再帰木,二分探索木,スケールフリーランダム木と正規トリーの混合物を考察した。これは一様ランダム再帰木のカットツリーのためのBertoin(Probab Stat5(2015),478 488)の結果の拡張をもたらし,また,頂点の多重分離に及ぼすKubaとPanholzer(オンラインJ肛門Combin(2014),26)のいくつかの結果を一般化することを可能にする。アプローチは破壊過程とBernoulliボンドパーコレーションの間の密接な関係,樹木の他のクラスのカットツリーを研究するための有用であるかもしれない,に依存している。Copyright 2017 Wiley Publishing Japan K.K. All Rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *二分探索 ,  パーコレーション ,  確率測度 ,  位相幾何学 ,  家系
準シソーラス用語： オンライン ,  分岐点 ,  Euclid距離 , 【Automatic Indexing@JST】

著者キーワード (4件)： ランダム木 ,  樹木の破壊 ,  パーコレーション ,  Gromov Prokhorov収束

分類 (2件)： 計算理論  (JB02000A) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： 大規模 ,  木