著者

伊東 利哉 武井 由智 垂井 淳

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.194, pp.39-46, 1999-07-21

参考文献数

13

---

置換族がk点独立性を持つとは, 直観的には, そこから置換を一様ランダムに選んだとき任意の異なるk点が任意の異なるk点に等確率に写像されることである. 類似概念として, 任意の異なるk点の像のなす相対順序が等確率にあらわれるという性質が定義でき, これをk順位独立性と呼ぶことにする. また, 任意の異なる高々k点の像の中で全ての点が等確率で最小値となる性質がk制限最小値独立性として定義されている. 本論文では, 集合{0,1,...,n-1}に作用する置換族Cが上記各独立性を満足するときの要素数∥C∥の限界を考察し, 以下の結果一(1)下界: k制限最小値独立性は∥C∥≧n-1, k順位独立性は∥C∥≧(n/2)^<&lfloor;k/4&rfloor;> がそれぞれ必要(2)上界: k制限最小値独立置換族は∥C∥= o((en)^k), k順位独立置換族は∥C∥=0(n^<k2/(21nk)>)でそれぞれ構成可能を示す.

著者

富田 悦次 高橋 治久 西野 哲朗 若月 光夫 垂井 淳

出版者

電気通信大学

雑誌

基盤研究(C)

巻号頁・発行日

2007

---

最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た.