コーダルグラフの完全列の列挙
スポンサーリンク
概要
- 論文の詳細を見る
長さ4以上のサイクルが必ず弦を持つグラフをコーダルグラフと呼ぶ.コーダルグラフでは,極大クリークの集合からクリーク木と呼ばれる特別な木構造を構築することができる.クリーク木の葉を繰返し取り除くとき,その逆順で与えられる極大クリークの列を完全列という.本論文では完全列の列挙問題を研究する.この問題は統計に応用を持つが,これまでに効率的な列挙アルゴリズムは知られていない.この問題の難しさは2つある.まず与えられたコーダルグラフに対するクリーク木は,一般には1つとは限らない.また,ある完全列が2つ以上のクリーク木から生成されることもある.したがって単純にそれぞれのクリーク木から可能な完全列をすべて生成する方法ではうまくいかない.本論文では,クリーク木を明示的に構成することなく,すべての完全列を列挙するアルゴリズムを提案する.本アルゴリズムはこの問題に対するはじめての多項式遅延のアルゴリズムである.特に本アルゴリズムは各完全列を平均的にO(1)時間で生成する.
- 社団法人電子情報通信学会の論文
- 2008-04-11
著者
-
松井 泰子
東海大学理学部
-
上原 隆平
北陸先端科学技術大学院大学
-
宇野 毅明
国立情報学研究所
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
宇野 毅明
東京工業大学 システム科学専攻
-
宇野 毅明
情報学研究所
-
宇野 毅明
東京工業大学経営工学専攻
-
宇野 毅明
東京工業大学システム科学
-
上原 隆平
北陸先端科学技術大学院大学 情報科学研究科
-
宇野 毅明
東京工業大学社会理工学研究科
-
宇野 毅明
国立情報学研
-
宇野 毅明
国立情報学研究所:総合研究大学院大学
関連論文
- A polynomial-time perfect sampler for the Q-Ising with local fields (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 頂点独立なノイズ付きQ-イジング模型のための多項式時間パーフェクトサンプラー
- 木の均一分割問題
- 再構成問題の計算複雑さ
- あみだくじの高速列挙
- 折紙の計算量的複雑さの研究 (小特集 折紙工学の現状と課題)
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- 最短路高速検索のための階層メッシュ疎化法
- 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- Polygons Folding to Plural Incongruent Orthogonal Boxes (Acceleration and Visualization of Computation for Enumeration Problems)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- じゃばら折りの複雑さに関する研究
- 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
- 複数の箱を折ることのできる展開図に関する研究
- 折り紙とコンピュータサイエンス(学生/教養のページ)
- コーダルグラフの完全列の列挙
- 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- スケールフリーグラフ上における局所情報を用いたランダムウォークについて
- 2部パーミュテーショングラフのバンド幅
- 航空路線問題に対する効率の良いアルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- プロープ区間グラフの拡張MPQ木表現
- 2部グラフとProbe区間グラフにおける木スパナー
- 2部グラフの部分クラスに対するGI完全性について
- 重み最大マッチングを求める並列近似アルゴリズム
- グラフの連結成分の個数と応用
- 弦グラフの一般化と、そのグラフ上での問題の難しさ
- ある投票ゲームのシミュレーション
- Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)
- 飛び出す絵本の複雑さ
- 単純多角形の生成に関する発見的手法(セッション2)
- グラフ上のボロノイゲームとその困難性(セッション1)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- 組合せ構造の列挙とサンプリング(代数、形式言語、計算システム理論とその応用)
- 負の重みに対応した高速頻出集合発見プログラムの開発(人工知能,データマイニング)
- 1-E-4 Web版訪問介護スケジュール作成支援システム(スケジューリング)
- 計算幾何学的な手法を用いた高速相同性計算手法
- グラフクラスと部分グラフ同型性
- 帯状の紙の折りたたみに関する最適化問題
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- 一般化KaboozleのNP完全性
- 折紙における決定不能問題
- 計算幾何学的な手法を用いた高速相同性計算手法
- 支配集合数え上げ問題とグラフクラス
- パス上のボロノイゲーム
- 帯状の紙の折りたたみに関する最適化問題
- 折紙における決定不能問題
- 電力取り引きにおける約定量決定問題の高速解法
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- ロジスティクスにおける最適化ツールの開発(交通・輸送(2))
- パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
- パターンマイニングの新しい落としどころ : クラスタリングを用いたパターンマイニング(コンピュータビジョンとパターン認識のための機械学習と最適化,一般)
- 一般化 Kaboozle のNP完全性
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- プトレマイオスグラフのラミナー構造とその応用
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- k-木のスケールフリー性に関する研究
- k-木のスケールフリー性に関する研究
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- Approximation algorithm for generating B^m × J contingency tables
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- Hoffmanパズル解の列挙と一般化に関する研究
- 複数の直方体を折れる共通の展開図に関する研究
- グラフクラスとアルゴリズム
- 冒険とOR(21世紀を最適化する女性たち)
- 分割表の列挙とグレブナー基底 (最適化の数理とアルゴリズム)
- 分割表の列挙とランダム生成 (グレブナ-基底の理論的有効性と実践的有効性)
- Integer Programming and Grobner Bases (Algebraic Combinatorics on Convex Polytopes)
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- 2部グラフの辺彩色を列挙するアルゴリズムの計算時間の解析
- 複数の直方体を折れる共通の展開図に関する研究
- ゲーム・パズルの計算量を示すための新しい枠組みについて(パズルとゲームの計算理論)
- 木の最小コスト点彩色の列挙と一意性について
- ある投票ゲームのシミュレーション