文献

J-GLOBAL ID：201702280102523165   整理番号：17A1497784

O(n)ビットを用いたDFSの双連結性,st番号づけとその他の応用【Powered by NICT】

Biconnectivity, st-numbering and other applications of DFS using O(n) bits

著者 (3件)： Chakraborty Sankardeep (The Institute of Mathematical Sciences, HBNI, Chennai, India) ,  Raman Venkatesh (The Institute of Mathematical Sciences, HBNI, Chennai, India) ,  Satti Srinivasa Rao (Seoul National University, Seoul, South Korea)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 90  ページ： 63-79  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 連結性試験と2エッジ連結性の問題を含むDFSのいくつかの古典的応用の空間効率的な実装を考察し、切断バーテックスおよび切断エッジの発見,n頂点とm辺に与えられた無向グラフGの連鎖分解とst番号づけを計算する。古典的アルゴリズムは典型的には各頂点でDFSといくつかのΩ(lg n)bitsof情報を使用した。Elmasryら(STACS 2015)によるDFSの実施最近のO(n)ビットに基づいて,DFSのこれらのすべての応用のためのO(n)ビット実装を提供する。提案アルゴリズムでは,いくつかの小さな定数c(c≦2)のためのO(m lg c n lg lg n)時間を要する。筆者らの実装の中心は,DFS木の簡潔な表現と連結部分木にDFS木の空間効率の良い分配,他の空間効率の良いグラフアルゴリズムを設計するための独立した関心のあるものである。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 無向グラフ ,  アルゴリズム ,  *連結性 ,  輪郭近似
準シソーラス用語： グラフアルゴリズム ,  部分木 , 【Automatic Indexing@JST】

著者キーワード (8件)： DFS ,  空間効率的なグラフアルゴリズム ,  双連結性 ,  の2-エッジ連結性 ,  stナンバリング ,  疎スパニング連結部分グラフ ,  位相幾何学的なソーティング ,  Lowpoint

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (5件)： ビット ,  連結性 ,  ST ,  番号 ,  応用