Finding Minimal Unsolvable Structures for Constructive Generation of Graph 3-Colorability Instances
スポンサーリンク
概要
- 論文の詳細を見る
We have developed the method for systematically generating very hard graph 3-colorability (3COL) instances to clarify phase transition mechanism of combinatorial search problems. In our method, 3COL instances can be generated by repeatedly embedding minimal unsolvable graphs (MUGs). In this paper, we find larger-scale MUGs, which are necessary for our generation method, using genetic algorithms (GAs). We also experimentally demonstrate that the computational cost to solve our 3COL instances generated by using MUGs found by GAs is of an exponential order of the number of vertices and our instances are extraordinarily harder than randomly generated instances.
- 一般社団法人 人工知能学会の論文
著者
関連論文
- 3C-7 連続断面画像集合からの3次元領域抽出のためのシステム開発(画像処理・認識,一般セッション,人工知能と認知科学)
- 5Z-3 実世界指向の3D形状データ変換手法の提案(モデリング,学生セッション,インタフェース)
- 5C-4 セルオートマトンによる仮想都市空間内の土地利用変化シミュレーション(複雑系,一般セッション,人工知能と認知科学)
- 5S-5 Binary CSPのための制約違反最小化戦略に基づくハイブリッド型Ant Systemの提案(認知・推論・探索,学生セッション,人工知能と認知科学)
- 5S-4 極小非可解構造の埋め込み操作による3COLインスタンスの組織的生成(認知・推論・探索,学生セッション,人工知能と認知科学)
- 1ZE-4 制約充足に基づく図面理解システムのGUI開発(CG:モデリング,探索,学生セッション,インターフェース)
- 3V-1 マルチエージェント型交通シミュレータと歩行者エージェントの導入(マルチエージェント(1),学生セッション,人工知能と認知科学)
- 1V-5 蟻の集団を用いたBinaryCSPの解法(学習・推論,学生セッション,人工知能と認知科学)
- 6C-7 仮想都市における交通シミュレーションによる動的経路選択の有用性の検証(ニューラルネット・マルチエージェント,一般セッション,人工知能と認知科学)
- 極小非可解構造に基づく3COLインスタンスの組織的生成(人工知能,認知科学)
- 稜線の配置に制約を持つメッシュモデルの変形手法(セッション1:モデリング)
- 1ZF-2 B-spline曲面の制御点の削減手法と削減後の制御点を用いた曲面生成手法(CG:面,学生セッション,インターフェース)
- 2F-4 コンピュータマネキンを用いた高齢者の歩行時における転倒動作のシミュレーション(CG:一般,一般セッション,インターフェース)
- 2F-3 特徴点・特徴ライン位置を用いた個人用人台作成ソフトの開発(CG:一般,一般セッション,インターフェース)
- 3次元情報抽出のための疑似透視投影モデル因子分解法と透視投影モデル最小二乗法の比較(セッション1:CG一般,テーマ:エンターテイメントのためのCGおよびCG一般)
- 有向グラフの類似性を用いた問題解決プロセス評価法 : 「システム設計II」での実践評価
- ファジィグラフの類似性の定量化とその応用
- 有向グラフの類似性を用いた問題解決プロセス評価法 : 「システム設計II」での実践評価
- ファジィグラフの類似性の定量化とその応用
- バブル・メッシュ法によるメッシュ制御法の提案(セッション4:製品設計への応用,テーマ:エンターテイメントのためのCGおよびCG一般)
- e-Notebook における情報検索手法の開発
- Web ページを利用した学習のための e-Notebook システムの開発
- Web ベース学習のためのコミュニケーション環境の搆築
- 学習進捗状況の把握を支援する電子カルテシステム
- 公開範囲を指定可能な学習成果物発信システム
- 情報活用能力に応じたインターネット利用環境の構築(II)
- 情報活用能力に応じたインターネット利用環境の構築(II)
- 3D 教材開発用オーサリングツールの開発
- 教材評価の収集機能を有する Web 教材配信システムの開発
- 教材評価の収集機能を有する Web 教材配信システムの開発
- 1W-3 連結度に注目した難しい3彩色インスタンスの組織的生成(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 欠損データのある評定尺度データの分析法
- 欠損データのある評定尺度データの分析法
- 教材評価機能を有するWeb教材ディレクトリサービスシステム
- F-023 制約充足問題のためのランク付け機能を有するACOの局所探索による解候補育成(F分野:人工知能・ゲーム,一般論文)
- 1W-2 制約充足に基づく勤務シフトスケジューリング(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- F-017 Binary CSPのための制約違反最小化戦略のハイブリッド型Ant Systemの効果(人工知能・ゲーム,一般論文)
- 認知マップを利用した合意形成型グループウェアシステム(IV)
- 認知マップ作成・表示支援システムの利用と評価
- 項目の重要度を考慮した認知マップ表示法
- 認知マップを利用した合意形成型グループウエアシステム
- 合意形成型グループウエアシステム : 認知マップからのアプローチ
- 教育評価用 Java クラスライブラリの開発
- ロジカルフローテストの測定法に関する一考察
- XML様テキスト構造を持つインプラントJPEGを用いた静止画プレゼンテーションシステム
- 分散共有仮想空間におけるコミュニケーションシステムの開発
- 仮想空間利用の学習環境構築のためのプラットフォームの開発
- 3D教材開発用フレームワークの開発(e-Learningコンテンツの編集と再利用/一般)
- 3D教材開発用共通プラットフォームの提案(教育支援システム/一般)
- チームティーチングのための電子カルテシステムの開発 : 教師移動マップの作成
- CD ブータブル OS による授業実践 : 実践結果と自動再構成システムの検討
- 動的なグループ構成が可能な KJ 法システムの開発
- プレゼンテーション用 CD-ROM 作成のための自動再構成システム
- データ図示化のためのタグライブラリの作成
- 課題系列化法の IRS グラフへの適用
- 個々の学習者の視点に基づいた検索支援システムの開発
- インターネット学習用Webブラウザの設計と開発
- 学習者の能力に応じた情報教育実践環境の構築
- インターネット学習用 Web ブラウザの設計と開発
- インターネット学習用 Web ブラウザの設計と開発
- 学習者の能力に応じた情報教育実践環境の構築
- バーチャルスクールにおけるネットワークコミュニケーションの実践と評価
- (77)WWWを利用した情報創造・発信技術育成のための教育実践 : 情報工学科情報工学実験での事例(第19セッション 教材の開発(I))
- 教材構造グラフ作成・表示支援システムの開発
- KNOPPIXの教育利用と実践報告(2) : 講義資料の収録とユーザインタフェイスの改善
- マイコン活用教材を軸としたフィードバックモデルの学習に関する実践教育
- F-034 グラフ彩色インスタンス生成のためのGAに基づく極小非可解構造の導出(知能システム,F分野:人工知能・ゲーム)
- Finding Minimal Unsolvable Structures for Constructive Generation of Graph 3-Colorability Instances