The Diameter of Dense Random Regular Graphs
という単著の論文がSODA18に採択されました.
SODAは Symposium on Discrete Algorithms という理論的な国際会議で, コンピュータ科学において「トップカンファレンス」と呼ばれるもので, なかなか通すのが難しいと言われています. 今年のSODA17には通した日本人が1,2人しかいなかったと記憶しています. 今年はバルセロナでの開催でしたが, 来年のSODAはニューオリンズです. 他にもFOCS, STOCなどが有名です.
通した論文の内容はランダム正則グラフの直径についてのものです. ランダム正則グラフは次数が定数の場合は直径が漸近的(頂点数→無限)に"最適" (i.e. Moore Boundから得られる直径の理論下界との比が1に収束)で, HPCのネットワークトポロジーとしても有用であることが知られています. しかし次数が頂点数とともに増加する場合はその直径がどうなるかはexplicitには知られていませんでした. (実際にはMoore Bound と最近発表された定理を拾ってくるとだいたいのケースでは上界と下界が得られます). 今回の論文はそのようなランダム正則グラフの直径について, 次数dが $d=\beta \cdot n^{\alpha}$ ($n$は頂点数) の場合だとその直径が $\lfloor \alpha^{-1} \rfloor + 1$ となることを証明しました (研究の本質的な点は, 上記の次数を持つランダム正則グラフに対してMoore Boundから得られる下界と上述の定理から得られる上界の間のギャップに関する問題を解決したという点にあります)
-
競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介し...
-
概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま... -
0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます. 1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ...