線形マトロイド・グラフアレンジメント・半順序での数え上げ問題に対する組合せ的・幾何的アプローチ
スポンサーリンク
概要
- 論文の詳細を見る
グラフに関する典型的な#P困難な問題に対して, 関根, 今井, 谷[12,13]は, 中規模のサイズの問題をBDDを用いて解く新しいアプローチを与えている. 本論文では, それを他の代表的離散構造である線形マトロイド, グラフに対するアレンジメント, 半順序に関する数え上げ問題に拡張する. まず, 2値・3値マトロイドについては, 与えられた台集合の対応のもとで同型判定が多項式時間でできることを示して, その基底を表現するBDDが出力サイズに比例する時間で構成できることを示す. このBDDを用いて, 線形マトロイドのTutte多項式, 線形符号の重み生成多項式を計算することができる. 次に, 実数ベクトル空間の線形マトロイドについて, 対応する幾何構造であるアレンジメントを構成するアルゴリズムを用いて, そのTutte多項式が効率よく計算できることを示す. また, それをグラフアレンジメントの問題に特化させた場合に対応するグラフの無閉路向き付け問題や半順序のイデアル問題についてもアルゴリズムを与える.
- 一般社団法人情報処理学会の論文
- 1996-03-15
著者
-
岩田 覚
京都大学数理解析研究所
-
吉田 研秀
東京大学理学部
-
今井 浩
東京大学理学部情報科学科
-
関根 京子
東京大学理学系研究科情報科学専攻
-
吉田 研秀
東京大学理学系研究科情報科学専攻
-
今井 浩
東京大学理学系研究科情報科学専攻 Erato今井量子計算機構プロジェクト 科学技術振興事業団
-
関根 京子
東京大学理学系研究科
関連論文
- 非線形時変回路に対する混合方程式の組合せ論的解析 : グラフ構造による順良指数の特徴付け (21世紀の数理計画 : アルゴリズムとモデリング)
- 劣モジュラ費用集合被覆問題 (21世紀の数理計画 : アルゴリズムとモデリング)
- 「距離の暴虐」を超えて
- 難読化コンパイラのユーザによる保護強度調整機構(コンピュータシステム技術,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))
- FPGA基板を用いたモンテカルロ碁の高速化(アクセラレーションと回路設計,2009年並列/分散/協調処理に関する『仙台』サマー・ワークショップ(SWoPP仙台2009))
- 動的逆アセンブル手法の高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- 高信頼性マルチホーミング通信方式(ネットワーク,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- ガウス写像に基づく初期曲面のための曲面制御点の生成
- 2-D-3 混合行列束のKronecker標準形の組合せ論的解析(離散・組合せ最適化(5))
- 電気回路の混合解析における微分代数方程式の指数最小化 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- 双対変数を用いたA^*両方向探索アルゴリズムと経路誘導における最短路問題
- 経路誘導における最短路問題の解法について
- 簡潔データ構造による全文検索のハードウェアを用いた高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- 分散共有メモリアクセスの優先度制御(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- トランザクショナルメモリのための性能評価手法(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- 連載：理学のキーワード : 第29回
- 理学部研究ニュース
- 2-E-3 混合多項式行列の小行列式の最大次数を計算する組合せ緩和法(離散最適化(1))
- プログラミング言語MLのCUDA向け拡張
- SIMD型計算機向けループ自動並列化手法
- 動的推定によるプリフェッチ量最適化
- Webブラウザを用いた長距離データ転送の高速化
- コヒーレントでないメモリシステムへのアーキテクチャ支援
- Ruby用仮想マシンにおけるAOTコンパイラ
- メニーコアプロセッサ向き共有キャッシュ配分方式
- マップ型履歴を用いたプリフェッチ方式とキャッシュ置換方式の協調動作
- 「距離の暴虐」を超えて
- Index Reduction for Differential-Algebraic Equations by Discrete Optimization Techniques(Mathematical Sciences for Large Scale Numerical Simulations)
- 線形マトロイド・グラフアレンジメント・半順序での数え上げ問題に対する組合せ的・幾何的アプローチ
- 均質システムの自律可制御性解析
- 凸費用劣モジュラ流に対する容量スケーリング法
- 二分決定グラフのトップダウン構成法と並列化
- 超並列準汎用計算機GRAPE-DRによる重力多体問題シミュレーションおよびLU分解
- オフライン環境における多様性の高い実行時自己改変ソフトウェア(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- 日米間QoSによるLFN高速化実験と分散KVSの構築(研究発表,ネットワーク研究開発テストベッド運用・利用,一般)
- TCPによる長距離ディスク間データ転送の高速化
- Computational Geometry on Statistical Manifolds for Clustering : Extended Abstract (Models of Computation and Algorithms)
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 部分的試行に基づく動的共有キャッシュ分割方式
- GeForce GTX 280 vs. Cell
- 置換データの性質に着目した動的キャッシュパーティショニング
- 追い出しラインに着目したプリフェッチスロットリング手法
- フィードバックを用いたハイブリッド・プリフェッチ方式
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子計算の科学
- 量子エントロピーの離散構造
- 劣モジュラ費用集合被覆問題
- 三角形分割の最適性と整数計画による定式化
- Optimality and Integer Programming Formulations of Triangulations in General Dimension
- 三角形分割の最適性と整数計画による定式化
- パケット喪失履歴に基づいたTCP幅輳制御方式(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- 混合行列束の Kronecker 標準形の組合せ論的解析
- 混合行列束のKronecker標準形の組合せ論的解析
- 複数の生物学的配列の準最適アラインメントについて
- 地理情報システムの標準化動向と参照モデル
- AT-3-2 劣モジュラ最適化と近似アルゴリズム(AT-3.コンカレントシステム理論の新しい流れ,チュートリアルセッション,ソサイエティ企画)
- "Peter Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing,Vol.26,No.5, pp.1484-1509, 1997 (20世紀の名著名論)
- 線形計画問題に対する乗法的罰金関数法の拡張
- バケット手法,Peano曲線を用いた平面マッチング,巡回セールスマン問題に対する近似算法の理論的評価
- 足切り横断ポリマトロイドに対するネットワーク算法
- 最大流算法の実際的評価
- 5.量子計算と最適化(量子情報処理パラダイム)
- 量子情報処理パラダイム : 1.量子計算の基礎
- 最短路算法の実際的評価と新バケット法
- 劣モジュラ流問題に対するコストスケーリング算法(組み合わせ最適化(1))
- 埋め込まれた曲面の接続可能性(計算幾何学と離散幾何学)
- 1-A-9 劣モジュラ最適化(計算と最適化(1))
- 2-C-4 独立偶因子の組合せ的アルゴリズム(離散最適化(3))
- KSMAP「OR若手の会」の紹介
- 一般グラフのDulmage-Mendelsohn型分解(グラフ・ネットワーク(2))
- 選択組立におけるマッチング算法(組合せ最適化(2))
- RL-001 FPGAを用いた広帯域高遅延ネットワーク向けの利用可能帯域推定(L分野:ネットワーク・セキュリティ,査読付き論文)
- Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
- 4.先端グローバルR&D網の構築と国際協調アプリケーションの展開 : JGN2の国際連携活動(オープンリサーチ型次世代ネットワーク技術への挑戦-National Project JGN2 4年間のFact Sheets-)
- 1方向確率的可逆および1方向量子1カウンタオートマトン (代数系,形式言語および計算理論)
- ランダマイズドクラスタリングアルゴリズムに関する実験結果について
- 点集合を分散の総和が最小となるようにk個のクラスターに分割するアルゴリズム
- Polytopes of linear programming relaxation for triangulations
- Grobner Bases of Acyclic Tournament Graphs and Hypergeometric Systems on the Group of Unipotent Matrices (Algorithms for D-modules)
- Complexity of Grobner Bases for Toric Ideals of Acyclic Tournament Graphs (Foundations of Computer Science)
- BDDを用いたデータマイニング
- 量子計算機シミュレーションシステム (新しいパラダイムとしてのアルゴリズム工学)
- 高性能な8倍精度浮動小数点演算機構の実現
- 多種言語処理系性能の評価に適したベンチマークプログラム
- 不要キャッシュブロックのパーティショニングによる排除方式
- HPC Ruby:静的解析に基づくRubyの高度最適化コンパイラ
- BTBへのBimode Cascading手法適用による分岐先アドレス予測の高効率化
- 多様な履歴の利用による分岐予測精度の向上
- 2010年度論文賞の受賞論文紹介 : 低次キャッシュとプリフェッチ
- 実用的なRuby用AOTコンパイラ
- コンピュ-タ-と時間 (特集/変わりゆく時間意識)
- 三角形分割の周辺 (フォーラム:現代数学の風景/組合せ論を育む土壌)
- 輸送問題
- 21世紀を変える!?量子コンピュータの夢--確率的挙動を使ったより強固な情報インフラ (特集2 量子コンピュータ)