コーダルグラフサンドイッチ問題とその応用
スポンサーリンク
概要
- 論文の詳細を見る
コーダルグラフは,統計学,数値計算法,最適化算法などの諸分野において,効率的な計算を行うことができる非常に重要なグラフクラスである.統計学においては,コーダルグラフはグラフィカルモデルが分解可能であるための必要十分条件として知られる.本稿では「コーダルグラフサンドイッチ問題」を取り扱う.コーダルグラフサンドイッチ問題は,包含関係にあるグラフの対が与えられたとき,そのグラフに挟まれるコーダルグラフを探索する問題である.コーダルグラフサンドイッチ問題は一般にはNP完全問題である.本稿では特に,与えられるグラフの対の一方がコーダルである場合を考え,サンドイッチされるコーダルグラフの効率的な生成法について議論する.また,これらの応用について述べる.
著者
関連論文
- 対数優/劣モジュラ分布からのサンプリング (アルゴリズムと計算機科学の数理的基盤とその応用)
- A polynomial-time perfect sampler for the Q-Ising with local fields (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 頂点独立なノイズ付きQ-イジング模型のための多項式時間パーフェクトサンプラー
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- じゃばら折りの複雑さに関する研究
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- コーダルグラフサンドイッチ問題とその応用
- 第18回RAMPシンポジウムルポ(情報の窓)
- 対数優モジュラ分布からのサンプリング
- 平成20年春季研究発表会ルポ(情報の窓)
- パス上のボロノイゲーム
- マルコフ連鎖の完璧シミュレーション(超ロバスト計算原理とモデリング・シミュレーション)
- 電力取り引きにおける約定量決定問題の高速解法
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- Enumeration of Graph Sandwiches (Acceleration and Visualization of Computation for Enumeration Problems)
- 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
- 1-B-3 一般化メディアン安定結婚問題に対する乱択近似アルゴリズム(アルゴリズム)
- マルコフ連鎖モンテカルロ法における近似精度保証と完璧サンプリング法(研究会推薦博士論文速報)
- Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 複数の単位円による点集合の排他的被覆
- DS-1-16 弦グラフおよびその部分クラスの列挙(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- コーダルグラフのサンドイッチ列挙
- 1-B-14 線形計画問題を誤差無く解くソルバ(数理計画(1))
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法