抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
一般化ソーティング問題は,n要素を分類することを望んでいる標準比較ソーティングの制約されたバージョンであるが,ペアの部分集合だけを比較できる。形式的には,n要素v_{1,v_{n}にいくつかの既知のグラフG=(V,E)があり,その目標は,全ての比較(v_{i,v_{j})がEのエッジであるとのできるだけ少ない比較として,要素の真の次数を決定することである。真の秩序化がx_{1<x_{2}<.<x_{n}>{x_i}の頂点{v_i}の未知の置換,(x_i,x_{i+1})||E}の全てのi:このハミルトニアン経路は,ソーティングが実際に可能であることを保証した。本研究では,ランダムグラフと最悪ケースグラフの両方に対する一般化ソーティングに対する限界を改善した。Erdo′′s-RenyiランダムグラフG(n,p)(ソーティングを確保するために追加される有望なハミルトニアン経路を有する)に対して,著者らは,期待O(nlg(np))比較による一般化ソーティングのためのアルゴリズムを提供して,それは質問複雑性のために最適であることを証明した。これは,Tilde{O(min(n√np,n/p{2})}比較を用いた,Huang,Kannan,Khanna(FOCS2011)の最良の既知アルゴリズムよりも強く改善した。n頂点とmエッジを持つ任意のグラフG(約束ハミルトニアン経路で)に対して,チルデO(√mn)比較による一般化ソーティングのためのアルゴリズムを提供した。これは,最小(m,O(n3/2))比較を使用するHuang et al.Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
