近似的証明ラベリング方式【JST・京大機械翻訳】

Censor-Hillel Keren; Paz Ami; Perry Mor

文献

J-GLOBAL ID：202002227777822395 整理番号：20A0476135

近似的証明ラベリング方式【JST・京大機械翻訳】

Approximate proof-labeling schemes

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A0476135&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A0476135&from=J-GLOBAL&jstjournalNo=T0022A") }}

著者 (3件)： , ,
資料名：
巻： 811 ページ： 112-124 発行年： 2020年
JST資料番号： T0022A ISSN： 0304-3975 CODEN： TCSDIQ 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：オランダ (NLD) 言語：英語 (EN)

筆者らは,分散ネットワーク上でのボolean述語の検証の新しいモデルを研究した。ネットワーク構成を与えると,証明ラベリング方式(PLS)モデルは各ノードに与えられるラベルの形式における分散証明を定義し,すべてのノードは局所的に,ネットワーク構成がそれらの近傍とラベルを交換することにより望ましいボolean述語を満たすことを局所的に検証する。この方式の証明サイズはラベルの最大サイズであると定義される。本研究では,近似的な証明ラベリング方式(APLS)モデルを定義することにより,このモデルを拡張した。この新しいモデルにおいて,検証のための述語は,構成Fのファミリーに対するψ,φ:F→Nのようなψ≦φの形である。情報的に,このモデルで考慮された述語は,構成の2つの値の間の比較である。PLSモデルにおけるように,ノード交換ラベルは,述語を局所的に検証するためにラベルを交換し,ネットワークが述語を満足するかどうかを受け入れなければならない。この健全性条件は近似比αによって緩和されるので,ψ>αφがいくつかのノードが拒絶しなければならない。2つの検証問題に焦点を合わせた:グラフの直径に関する上限と下限,および与えられたマッチングの最大性。これらの問題に対して,すべてのグラフ構造に適用した最初の結果を示した。著者らの新しいAPLSモデルにおいて,証明サイズはPLSモデルにおける同じ述語の証明サイズよりはるかに小さいことを示した。さらに,近似比と証明サイズの間にトレードオフがあることを証明した。最後に,PLSモデルにおける最大基数マッチングのための最初の一般的結果を示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

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

著者キーワード (4件)： , , ,

計算理論 , グラフ理論基礎

, ,

前のページに戻る