最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
スポンサーリンク
概要
- 論文の詳細を見る
正方形を縦横それぞれn分割してできる(n+1)×(n+1)グリッドグラフにおいて、対角の2頂点を結ぶパスの数はnに対して急激に増大する。例えばn=10に対しては1024もの数となり、もはや一つずつ列挙するようなことはできない大きさである。これまでにKnuthのアルゴリズムに基づく方法でn=21までのパス数が計算されているが、我々はグリッドグラフの性質を利用して計算速度と使用メモリを大幅に改善し、n=23までの計算に成功した。
- 2013-02-22
著者
-
宇野 毅明
国立情報学研究所
-
湊 真一
NTT未来ねっと研究所
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
Ntt Lsi研究所
-
湊 真一
函館五稜郭病院
-
湊 真一
Ntt光ネットワークシステム研究所
-
岩下 洋哲
株式会社富士通研究所
-
宇野 毅明
東京工業大学 システム科学専攻
-
宇野 毅明
東京工業大学
-
宇野 毅明
情報学研究所
-
宇野 毅明
東京工業大学経営工学専攻
-
宇野 毅明
東京工業大学システム科学
-
湊 真一
Ntt 未来ねっと研
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
Ntt Lsi 研究所
-
川原 純
科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
宇野 毅明
国立情報学研究所(nii)
-
宇野 毅明
東京工業大学社会理工学研究科
-
Minato Shin-ichi
Graduate School Of Information Science And Technology Hokkaido University
-
湊 真一
北海道大学大学院情報科学研究科:jst Erato湊離散構造処理系プロジェクト
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理プロジェクト
-
岩下 洋哲
科学技術振興機構ERATO湊離散構造処理系プロジェクト
-
宇野 毅明
国立情報学研
-
宇野 毅明
国立情報学研究所:総合研究大学院大学
-
中澤 吉男
アマチュアプログラマー
-
川原 純
奈良先端科学技術大学院大学情報科学研究科
-
岩下 洋哲
科学技術振興機構ERATO湊離散構造処理系プロジェクト|北海道大学大学院情報科学研究科
-
岩下 洋哲
科学技術振興機構
-
湊 真一
北海道大学 大学院情報科学研究科
-
湊 真一
科学技術振興機構ERATO:早稲田大学:北海道大学
-
湊 真一
京都大学大学院情報学研究科:科学技術振興機構ERATO湊離散構造処理プロジェクト
-
川原 純
奈良先端科学技術大学院大学
-
湊 真一
北海道大学 大学院 情報科学研究科
関連論文
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 木の均一分割問題
- 最短路高速検索のための階層メッシュ疎化法
- 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- コーダルグラフの完全列の列挙
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- JGNを介した大規模映像配信プラットフォーム(新しいトラヒックモデルと性能評価及び一般)
- B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察
- B-7-47 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験
- B-7-46 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング
- B-7-45 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式
- 論理合成技術
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDD(二分決定グラフ)とその応用
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- 負の重みに対応した高速頻出集合発見プログラムの開発(人工知能,データマイニング)
- 1-E-4 Web版訪問介護スケジュール作成支援システム(スケジューリング)
- 計算幾何学的な手法を用いた高速相同性計算手法
- グラフクラスと部分グラフ同型性
- 計算幾何学的な手法を用いた高速相同性計算手法
- 支配集合数え上げ問題とグラフクラス
- 電力取り引きにおける約定量決定問題の高速解法
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- ロジスティクスにおける最適化ツールの開発(交通・輸送(2))
- パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
- パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- データインテンシブコンピューティング : その2 頻出アイテム集合発見アルゴリズム(知能コンピューティングとその周辺〔第2回〕)
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- ワイルドカードを許した極大モチーフの列挙アルゴリズム
- 大規模データ処理に対するアルゴリズム理論からのアプローチ (第20回 回路とシステム軽井沢ワークショップ論文集) -- (新世代の計算限界)
- 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)
- 大規模木構造データからの頻出部分構造パターン発見アルゴリズム(文字列アルゴリズム)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法
- 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般)
- 2部クリークを用いたclosed item setの効率的な列挙(「21世紀の知識情報科学に向けて」,及び一般)
- 双対化を用いた新しい極大頻出アイテム集合の計算(「21世紀の知識情報科学に向けて」,及び一般)
- 中小規模スタッフスケジューリング問題における調整の容易なスケジュール作成に関する研究
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- DK-2-4 大規模データに対する高速類似性解析手法の構築(DK-2.JSTさきがけセッション:人と社会のための情報処理,ソサイエティ企画)
- DK-2-4 大規模データに対する高速類似性解析手法の構築(DK-2.JSTさきがけセッション:人と社会のための情報処理,ソサイエティ特別企画,ソサイエティ企画)
- 擬似クリークを列挙する多項式時間遅延アルゴリズム
- RF-006 負の重みに対応した高速頻出集合発見プログラムの開発(人工知能・ゲーム,査読付き論文)
- Genome Homology Visualization by Short Similar Substring Enumeration (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-18 ハミング距離の短い文字列ペア列挙アルゴリズムと解析ツール(組合せ論)
- 1-A-4 修正を前提としたExcelベースのスタッフスケジューリングツールの開発(つくばOR学生発表(5))
- スタッフスケジューリングにおける修正しやすさを考慮した解の分析 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- 1-B-8 スタッフスケジューリングにおける修正しやすさを知る為の実験とその考察(スケジューリング(2))
- 1-B-9 部品の取り外しを考慮した仕掛り在庫と受注の高速マッチング(スケジューリング(2))
- 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
- RA-003 修正作業を効果的に支援するExcelベースのスタッフスケジューリングツールの開発(モデル・アルゴリズム・プログラミング,査読付き論文)
- ゲノム情報学における高速データ処理
- 列挙アルゴリズム(新・ORの図解,学会創立50周年記念号)
- 列挙を用いたモデリングの進展(モデリング-さまざまな分野,さまざまな視点から-)
- 近年の列挙技術の進展 : 計画立案と解法(ここまで使える数理計画法)
- DS-1-16 弦グラフおよびその部分クラスの列挙(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 頻出パターンの高速列挙
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 写像枝を用いた系列二分決定グラフ (Theoretical Foundations of Computing)
- 木に含まれる限定サイズ部分木の列挙 (コンピュテーション)
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化 (Theoretical Foundations of Computing)
- 系列二分決定グラフを操作するための豊富な演算体系の構築 (Theoretical Foundations of Computing)
- ベイジアンネットワークとZDDに関する最近の研究状況について (特集 「ベイジアンネットワークとその応用」および一般)
- 招待講演 フロンティア法 : BDD/ZDDを用いた高速なグラフ列挙索引化の技法 (情報ネットワーク)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 最先端の開拓者たち 湊真一氏 北海道大学大学院 情報科学研究科 教授 世界的権威が認めた超高速アルゴリズム 電力危機に挑む
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- D-1-6 マッチングアルゴリズムを用いた匿名化手法の提案(D-1.コンピュテーション,一般セッション)
- 最適化から見たデータマイニング(活躍する機械学習)
- DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
- 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
- 木に含まれる限定サイズ部分木の列挙
- 運用コストを重視した最適化 : 小規模な事業所で運用可能なシステムを考える(論文・研究レポート)
- 隣の芝は青くない
- 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム
- 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム(一般)