卒業研究ページ

卒業研究
最大クリーク問題を解く新しい高速なアルゴリズムの提案と従来のアルゴリズムとの実行時間比較実験

概要
中央大学の江口氏の研究を基に、これを上回る新たなアルゴリズムを考案・実装し、電気通信大学の富田教授によって提唱されたアルゴリズムよりも高速化することを目指す。

＜作成したファイル＞
・基本アルゴリズムdfmax
dfmax.cpp
dfmax2.cpp
dfmax3.cpp
dfmax4.cpp
dfmax5.cpp

・富田教授のアルゴリズムMCQ
color1.cpp(意味記述のみ)
color2.cpp
color3.cpp
color4.cpp
color5.cpp(ここから正確なアルゴリズム)
color6.cpp
color7.cpp(β)

・江口氏のアルゴリズムCLIQUE
clique1.cpp
clique2.cpp
clique3.cpp(β)

・独自アルゴリズムDEGCLQ
addeg1.cpp
addeg2.cpp
addeg3.cpp
addeg4.cpp
addeg5.cpp
addeg6.cpp
addeg7.cpp
addeg8.cpp
addeg8a.cpp(addeg撤廃)
addeg9.cpp
addeg10.cpp
added11.cpp

・レジュメ
TeX　 DVI　 PDF

・プレゼン
プレゼンテーション
pdf版

・スクリプト
同一ディレクトリ内の全gwファイルにプログラムを実行するシェルスクリプト

・その他
ランダムグラフ作成プログラム

・実行結果の一部(不定期更新)
c-fat500-1.gw.result

(研究室内部者用記述)
研究に使用したその他のファイルなどは、flsvr1の/home/shared/g-2006/s5402031hide/を参照してください