有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成

スポンサーリンク

概要

論文の詳細を見る
伊東・武井・垂井[7, STOC'03]は,置換族〓⊆S_nがk-制限最小値独立であならば|〓|=Ω(n^<[(k-1)/2]>)が成り立ち,k-順位独立であるならば|〓|=Ω(n^<[(k-1)/2]>)が成り立つことを示した.本論文では,アフィン幾何を用いて,そのサイズが|〓|= O(nlg^2n)となる3-制限最小値独立置換族〓⊆S_nおよび|〓|=O(nlg^3n)となる4-制限最小値独立置換族〓⊆S_nを構成するとともに,射影幾何を用いて,そのサイズが|〓|= O(n^3lg^6n)となる4-順位独立置換族〓⊆S_nを構成する.定義より,k-順位独立はk-制限最小値独立より強い概念であることは明らかであるが,本論文で構成する4-制限最小値独立置換族は,4-順位独立が4-制限最小値独立より真に強い概念であることを保証する.
社団法人電子情報通信学会の論文
2003-06-11

著者

関連論文

もっと見る

スポンサーリンク