最大重みクリーク問題に対する局所探索法(アルゴリズムとデータ構造・計算複雑度)
スポンサーリンク
概要
- 論文の詳細を見る
最近我々は,最大クリーク問題(Maximum Clique Problem, MCP)に対して,可変深度探索に基づくk-opt局所探索法(KLS)を提案し,DIMACSのベンチマークグラフに対して良好な結果を示した. MCPを一般化した最大重みクリーク問題(Maximum Weight Clique Problem, MWCP)に対してKLSを適用するには,KLSの探索過程における頂点の選択手続き(頂点選択方式)をMWCP用に拡張することで可能になる.本論文では,MWCPを対象にした複数の頂点選択方式を示し,それらの組合せにより構成可能なKLSの性能を検証する.また,MWCPに対して最近提案された他の近似解法との比較を通して,KLSの有効性を示す.
- 2006-08-01
著者
-
舩曵 信生
岡山大学大学院自然科学研究科
-
成久 洋之
岡山理科大学工学部
-
片山 謙吾
岡山理科大学工学部情報工学科
-
南原 英生
岡山理科大学工学部情報工学科
-
舩曵 信生
岡山大学工学部通信ネットワーク工学科
-
貞松 政史
岡山理科大学工学部情報工学科
-
植松 康祐
岡山理科大学情報処理センター
-
南原 英生
岡山理科大学工学部
-
成久 洋之
岡山理科大学工学部情報工学科
-
成久 洋之
岡山理科大学
-
成久 洋之
Department Of Information & Computer Engineering Okayama University Of Science
-
小澤 克夫
岡山理科大学大学院工学研究科
-
貞松 政史
岡山理科大学工学部
-
濱本 明宏
岡山理科大学工学部情報工学科
-
井上 浩孝/成久
Graduate School Of Engineering Okayama University Of Science/department Of Information And Computer
-
片山 謙吾/成久
岡山理科大学工学部情報工学科
-
成久 洋之
岡山理科大学大学工学部情報工学科
-
南原 英生
岡山理科大学
-
片山 謙吾
岡山理科大学
-
舩曵 信生
岡山大学工学部
関連論文
- 多種料理の調理手順スケジューリングアルゴリズムの複数調理者への拡張 (人工知能と知識処理)
- 閲覧サイズに適応するWebページレイアウト最適化法でのアクセス性改善(ライフインテリジェンス,デジタルドキュメント,一般1,知識の共有・伝承・知的活用に関するシステム・技術,一般)
- 多様な閲覧サイズのためのWebページレイアウト最適化法の提案(一般,ルーチングシステム(適応ルーチング,QoSルーチング,マルチキャスト),ネットワークアプリケーション(IP-TV,ストリーミング,Web2.0),一般)
- ペアリングを用いた効率的な属性ベースグループ署名方式の提案(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- シーン対応分割によるマルチサーバビデオエンコードシステム(一般,ルーチングシステム(適応ルーチング,QoSルーチング,マルチキャスト),ネットワークアプリケーション(IP-TV,ストリーミング,Web2.0),一般)
- プロキシを用いた匿名認証システムの改良と匿名掲示板への応用
- オープンソースソフトウェアインストールマニュアル管理のためのWEBデータベースシステム(ユビキタス・モバイル学習環境/一般)
- スケーラブル無線メッシュネットワークのためのスマートアクセスポイント配置アルゴリズムの提案(ネットワークアーキテクチャ(オーバレイ,P2P,ユビキタスNW,スケールフリーNW,アクティブNW,NGN・新世代NW),次世代パケットトランスポート(高速Ethernet,IPoverWDM,マルチサービスパケット技術,MPLS),グリッド,一般)
- 室内環境向け無線メッシュネットワークでのアクセスポイント配置アルゴリズム(無線ネットワーク,高度プロトコル・ネットワーキング技術(IP及び高位レイヤルーチング・フィルタリング,マルチキャスト,品質・経路制御),IPNWの利用技術(P2P,P4P,オーバレイ,SIP,NGN),ネットワークシステム関連技術(システム構成法,インタフェース,アーキテクチャ,ハードウェア・ソフトウェア・ミドルウェア),一般)
- 無線メッシュネットワークのアクセスポイント配置アルゴリズムの高信頼化拡張(無線ネットワーク,高度プロトコル・ネットワーキング技術(IP及び高位レイヤルーチング・フィルタリング,マルチキャスト,品質・経路制御),IPNWの利用技術(P2P,P4P,オーバレイ,SIP,NGN),ネットワークシステム関連技術(システム構成法,インタフェース,アーキテクチャ,ハードウェア・ソフトウェア・ミドルウェア),一般)
- テスト駆動型開発手法によるJavaプログラミング教育支援システムの提案(e-Learningコンテンツ/一般)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムの改善(無線ネットワーク)
- プライバシを保護した授業評価アンケートの実装
- 仮想マシンモニタ"Xen"を用いたスケーラブルなWebサーバシステムの提案(NW管理,次世代NWアーキテクチャ,次世代NWのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,次世代NWサービス品質,一般)
- 署名生成・検証時間が一定であるメンバ失効可能グループ署名方式の公開鍵サイズの低減
- モバイルホストの負荷を軽減した失効機能をもつ匿名IEEE802.1X認証の実装
- 教育支援システムNOBASUでの文章作法オンライン検査機能(ユビキタス・モバイル学習環境/一般)
- スケーラブル無線メッシュネットワークの通信性能を極大とする最小スマートアクセスポイント配置 (ネットワークシステム)
- 閲覧サイズに適応する Web ページレイアウト最適化法でのアクセス性改善
- スケーラブル無線メッシュネットワークのための通信路構成最適化アルゴリズム(地上無線通信)
- WEBベースの教育支援システム"NOBASU"の拡張と評価(情報教育/一般)
- 無線メッシュネットワークのアクセスポイント間通信での優先度順リンク動作方式(トラヒックエンジニアリング,一般,トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- インターネットアクセス無線メッシュネットワークでの動作アクセスポイント選択アルゴリズムの提案(超高速ネットワーク及びインターネット一般,省エネルギーと超高速ネットワーク,一般)
- 署名者の負担を軽減した失効機能をもつペアリングを用いたグループ署名方式の実装
- 忙しい人の手料理支援のための献立選択およびまとめ買い選択アルゴリズム (人工知能と知識処理)
- プライバシ保護を目的としたグループ署名に基づくSSL/TLSプロトコルの実装
- ペアリングを用いた効率的な属性ベースグループ署名方式の提案(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- Webページレイアウト最適化法のオープンソースソフトウェア・インストールマニュアルへの適用 (ネットワークシステム)
- Webによるオープンソースソフトウェア・設定マニュアル自動生成法の提案 (ネットワークシステム)
- WDMリングネットワークのノード構成問題の展開
- 効率的に検証者ローカル失効確認ができるグループ署名方式の実装
- 無線メッシュネットワークのスループット最大化のための動作AP選択指標の検討 (無線通信システム)
- 無線メッシュネットワークのスループット最大化のための動作AP選択指標の検討 (ネットワークシステム)
- スケーラブル無線メッシュネットワークの通信性能を極大とする最小スマートアクセスポイント配置(オーバレイ,P2P,ユビキタスNW,スケールフリーNW,アクティブNW,NGN・新世代NW),次世代パケットトランスポート(高速Ethernet,IPoverWDM,マルチサービスパケット技術,MPLS),グリッド,一般)
- 多種料理の調理手順スケジューリングアルゴリズムの複数調理者への拡張(一般,「Webサービス・クラウド」及び一般)
- テスト駆動型開発手法のJavaプログラミング教育応用におけるテストコード提出機能
- A proposal of traffic control method with bandwidth usage estimation for real-time applications in wireless mesh networks (無線通信システム)
- An implementation of a pairing-based anonymous credential system with constant complexity (ネットワークシステム)
- ノード配置問題に対するアント最適化法 (ネットワークシステム)
- 無線メッシュネットワークにおけるリンク動作率による固定待機時間切り替え方式の提案 (ネットワークシステム)
- A proposal of traffic control method with bandwidth usage estimation for real-time applications in wireless mesh networks (ネットワークシステム)
- 調理手順最適化のための調理モデルの拡張と副調理者の役割変更の効果 (人工知能と知識処理)
- 多種料理の調理順最適化アルゴリズムの提案
- 無線メッシュネットワークでの高信頼アクセスポイント配置アルゴリズムの改良と経路可度指標の導入(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・User Network Interface,Homeネットワーク,一般)
- PeerCastにおける経路の動的変更機能の実装(次世代ネットワーク,SIP・プレゼンス,一般)
- 電子的なホワイトボードのセキュア化に関する研究(信号処理,符号化,知的マルチメディアシステム,一般)
- VNCにおける負荷分散と操作権限制御を目的としたプロクシの提案(次世代ネットワーク,SIP・プレゼンス,一般)
- PeerCastをベースとしたマルチメディア配信システムPeerStreamの構築とその評価((フォトニック)IPネットワーク技術, (光)ノード技術, WDM技術, 一般)
- 最大重みクリーク問題に対する局所探索法(アルゴリズムとデータ構造・計算複雑度)
- 忙しい人の手料理支援のための献立選択およびまとめ買い選択アルゴリズム(「コミュニティ上での知識の共有・再利用」及び一般)
- 調理手順最適化のための調理モデルの拡張と副調理者の役割変更の効果(「コミュニティ上での知識の共有・再利用」及び一般)
- 無線メッシュネットワークの室内環境でのアクセスポイント配置アルゴリズム(無線ネットワーク・センサネットワーク,インターネットトラヒック,TCP/IP,性能解析・評価,ネットワークモデル及び一般)
- 操作ログを用いたオープンソースソフトウェアのインストールマニュアル自動生成法の提案
- メモリカードのためのセキュアファイルシステムSASの提案と実装(モバイルコンピューティング,ユビキタス社会を支えるコンピュータセキュリティ技術)
- テスト駆動型開発手法の Java プログラミング教育応用におけるテストコード提出機能
- 多種料理の調理順最適化アルゴリズムの提案
- WEBページレイアウト最適化手法を適用したオープンソースソフトウェア異種マニュアルの統合 (ネットワークシステム)
- リモートI/O機器のための組込みLinux(次世代ネットワーク,SIP・プレゼンス,一般)
- CMSを用いたオープンソースソフトウェア利用マニュアル管理システムの提案 (教育工学)
- オープンソースソフトウェア・設定マニュアル自動生成システムの試作 (ネットワークシステム)
- 教育支援システムNOBASUの支援機能の拡張(協調学習・CSCL/一般)
- ゲートウエイにMIMOチャネルを用いた無線メッシュネットワークでのWDSクラスタ分割アルゴリズム (ネットワークシステム)
- Webを用いたマークシート方式テスト支援機能の実装 (教育工学)
- 無線メッシュネットワークでの動作アクセスポイント選択アルゴリズムの提案(地上無線通信,放送技術,通信技術の未来を築く学生論文)
- 複数ネットワークインターフェースを有するエンドホストでのサービス指向型ルーティングの実装(次世代ネットワーク,SIP・プレゼンス,一般)
- 所属無効化可能なグループ署名方式の素数情報を用いた高速化とその実装
- 無線メッシュネットワークの実用性向上を目的としたスマートアクセスポイントの構築(NW管理,次世代NWアーキテクチャ,次世代NWのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,次世代NWサービス品質,一般)
- ユーザ失効を考慮した匿名IEEE802.1X認証の実装(セッション3-B : 認証・報告)
- ユーザ失効を考慮した匿名IEEE802.1X認証の実装(セッション3-B : 認証・報告)
- 複数オープンソース間連携を要するインストールマニュアル自動生成法の提案(セッション5:知識・連携)
- ログファイルを利用したオープンソースソフトウェアのインストールマニュアル自動生成法の提案(情報教育/一般)
- ペアリングを用いた効率的なForward-Secureグループ署名方式の提案
- ペアリングを用いた効率的なForward-Secureグループ署名方式の提案
- Webによる学習管理システム向け4階層アーキテクチャの提案とNOBASUでの実装(セッション4:セキュリティーアーキテクチャ)
- 忙しい人のためのWebを用いた手作り料理支援システムにおける献立作成・調理手順最適化機能の実装(エンタテインメントを活用した学習環境/一般)
- Javaプログラミングの予約語学習のためのオンライン穴埋め問題機能の実装(エンタテインメントを活用した学習環境/一般)
- uClinux環境下でのOSレベル仮想化の実現(一般セッション1:オペレーティングシステム)
- ゲートウェイにMIMOチャネルを用いた無線メッシュネットワークでのWDSクラスタ分割アルゴリズム(トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- 無線メッシュネットワークのスループット最大化のための動作AP選択指標の検討(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークのスループット最大化のための動作AP選択指標の検討(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークにおけるリンク動作率による固定待機時間切り替え方式の提案(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- Webを用いたマークシート方式テスト支援機能の実装(エンタテインメントを活用した学習環境/一般)
- Webページレイアウト最適化法のオープンソースソフトウェア・インストールマニュアルへの適用(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- Webによるオープンソースソフトウェア・設定マニュアル自動生成法の提案(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークでのリアルタイム通信のための消費帯域推定によるトラヒック制御方式の提案(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 無線メッシュネットワークでのリアルタイム通信のための消費帯域推定によるトラヒック制御方式の提案(無線マルチホップネットワーク特集セッション,モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 計算量が一定となるペアリングベース匿名証明書システムの実装(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- ノード配置問題に対するアント最適化法(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- テスト駆動型開発手法を用いたJavaプログラミング学習システムでのコード検証方法の改善 (教育工学)
- 無線メッシュネットワークでの動作アクセスポイント選択アルゴリズムの提案
- WDMリングネットワークのノード構成問題の一般化
- ボランティアコンピューティングにおける結託攻撃のモデル化と性能評価(ネットワーク環境でのディペンダビリティ,及び一般)
- テスト駆動型開発手法を用いたJavaプログラミング学習システムでのコード検証方法の改善(教育・学習のICT化支援/一般)
- 無線メッシュネットワークのスループット最大化のための動作AP選択アルゴリズムの改良(ネットワークアーキテクチャ(オーバレイ,P2P,ユビキタスNW,スケールフリーNW,アクティブNW,NGN・新世代NW),次世代パケットトランスポート(高速Ethernet,IP over WDM,マルチサービスパケット技術,MPLS),グリッド,一般)
- テスト駆動型開発手法を用いたJavaプログラミング学習システムでの誤りコード指示機能の実装 (教育工学)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムのスマートアンテナ拡張の一般化 (ネットワークシステム)
- Webを用いたマークシート方式テスト支援機能の拡張 (教育工学)
- オープンソースソフトウェア利用マニュアル管理システムの開発と大学院演習への適用 (教育工学)
- Javaプログラミング学習支援システムの穴埋め問題機能の拡張と授業への適用 (教育工学)
- 多種料理の調理手順最適化アルゴリズムの拡張 (画像工学)