ツリー分解に基づく隣接ラベリング方式【JST・京大機械翻訳】

Banerjee Avah

プレプリント

J-GLOBAL ID：202202201563631171 整理番号：22P0026986

ツリー分解に基づく隣接ラベリング方式【JST・京大機械翻訳】

An adjacency labeling scheme based on a tree-decomposition

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年01月12日プレプリントサーバーでの情報更新日： 2022年01月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,グラフの隣接ラベリングの問題を検討した。有向グラフのファミリーを与えられた場合,この問題は,符号化ラベルからのみ頂点の隣接情報を解読できるようなファミリーの各メンバーに対する符号化復号化方式を決定することである。さらに,各ラベルの長さを短く(n,頂点数),符号化復号化スキームを計算的に効率的とする。簡単なツリー分解ベースの符号化方式を提案し,それを用いてサイズO(klogklogn)ビットの隣接ラベリングを与えた。ここで,kはグラフファミリーのクリーク幅である。また,結果をk-プローブグラフのある種のファミリーに拡張した。【JST・京大機械翻訳】

, , , , ,
, , 【Automatic Indexing@JST】

グラフ理論基礎

前のページに戻る