抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
適切な円形アーク(PCA)モデルは,Cが円で,Aが,その極値がペアワイズが異なるC上の介在物フリーアークのファミリーである対M=(C,A)である。モデルMは,各ペアに対して1頂点v(a)を持つダイグラフDを表し,bの始め点がaに属するように,弧a,b∈A(M)の各対に対して1つのエッジv(a)→v(b)を持つ。k≧0の場合,Dのk-thパワーD ̄kは,Dとv(a)→v(b)がD ̄kのエッジであり,Dにおけるv(a)からv(b)までの距離が最もkにあるとき,D ̄kのエッジである。ユニット円形アーク(UCA)モデルは,すべてのアークが同じ長さl+1を持つPCAモデルU=(C,A)である。l,Cの長さc,およびAのアークの極値が整数であるならば,Uは(c,l)-CAモデルである。i≧0では,Uのモデルi×Uを,アーク(s,s+l+1)と各アーク(s,s+l+1)を置換して得た。UがダイグラフDを表すならば,i×Uが0≦i≦kごとにD ̄iを表すとき,Uはk-乗算である。本論文では,kが入力として与えられるとき,PCAモデルMがk-乗算UCAモデルに等しいかどうかを決定するために,線形時間アルゴリズムを設計した。このアルゴリズムは,線形時間で認証できるMまたは負の証明書に等価なk-乗算UCAモデルUを出力する。著者らの主な技術的ツールは,k-乗算UCAモデルと等価であるそれらのPCAモデルの新しいキャラクタリゼーションである。k=1では,この特性化は,以前に知られているアルゴリズムよりも簡単な古典的表現問題のための新しいアルゴリズムを与える。【JST・京大機械翻訳】
