コーダルグラフのサンドイッチ列挙
スポンサーリンク
概要
- 論文の詳細を見る
コーダルグラフは大きさが4以上の誘導部分サイクルをもたないグラフとして定義される.グラフGとGの部分グラフGが与えられた時,Gの真部分グラフでかつGを真部分グラフとして持つようなコーダルグラフGをみつける問題は,コーダルグラフサンドイッチ問題と呼ばれ,NP-困難であることが知られている.我々は,GまたはGがコーダルグラフであれば,コーダルグラフサンドイッチ問題は容易に解くことが可能であることを示した.さらに,これを用いてGおよびGのいずれか一方がコーダルである場合に,Gの部分グラフであり,Gを部分グラフとして持つようなコーダルグラフをすべて列挙する問題のアルゴリズムを開発した.この結果は,著者らの以前の結果[5]の自然な拡張になっている.
- 一般社団法人情報処理学会の論文
- 2006-09-27
著者
関連論文
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- じゃばら折りの複雑さに関する研究
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- コーダルグラフサンドイッチ問題とその応用
- 第18回RAMPシンポジウムルポ(情報の窓)
- グラフクラスと部分グラフ同型性
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- パス上のボロノイゲーム
- 多変量離散分布とマルコフ連鎖モンテカルロ法(学生セッション)
- 1-D-13 Sampling from Logarithmic Separable Concave Distribution on Simplex
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4, 日本計算機統計学会第18回大会報告)
- 電力取り引きにおける約定量決定問題の高速解法
- 電力取り引きにおける約定量決定問題の高速解法(組合せ最適化(5))
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4)
- 離散化Dirichlet分布に従うPerfect Sampler(マルコフモデル)
- MCMC法による2×n分割表個数数え上げ(セッション5)(日本計算機統計学会第16回大会報告)
- Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 有限グラフ上のランダムウォークの脱乱択化
- 複数の単位円による点集合の排他的被覆
- DS-1-16 弦グラフおよびその部分クラスの列挙(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- コーダルグラフのサンドイッチ列挙
- 1-B-14 線形計画問題を誤差無く解くソルバ(数理計画(1))
- m×n分割表の近似数え上げスキームの提案(マルコフ連鎖)
- 2×n分割表のPerfect Sampling(マルコフ連鎖)
- m×n分割表の近似数え上げスキームの提案
- MCMC法による2×n分割表個数数え上げ(一般講演)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 無理数の遷移確率を許すランダムウォークの脱乱択化 (理論計算機科学の新展開)
- 森および連結全域部分グラフの乱択近似数え上げ (理論計算機科学の新展開)