符号理論と完全マッチング計数問題の接点について
スポンサーリンク
概要
- 論文の詳細を見る
与えられたグラフにおける完全マッチングの個数の計数することは数え上げ問題における代表的な困難問題であり,グラフを3-正則二部グラフに制限したもとでも#P-完全であることが知られている.本研究は,3-正則二部グラフの完全マッチング計数問題に対する,O^^〜(2^<5n/12>)時間の多項式メモリスペースアルゴリズムを提案する.このアルゴリズムは,グラフの閉路空間およびカット空間に対する符号理論的な解釈に基づいており,線形符号における主符号と双対符号の間の関係式(マックウィリアムス恒等式)を利用して完全マッチング計数問題をカットの重み分布計算に帰着することで高速なアルゴリズムを実現している.
- 2011-12-09
著者
関連論文
- 平均性能を指標とした改良型Index-less Indexedフラッシュ符号 (情報理論)
- 凸最適化を用いた同期CDMA方式におけるマルチユーザ検出法(フレッシュマンセッション,フレッシュマンセッション,一般)
- 証明書分散問題の近似可能性について
- 圧縮センシングにおける完全再現十分条件について
- Population protocolにおけるオラクルをもたない自己安定リーダー選挙問題の可解性に関して
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- P2Pネットワークにおける決定性減衰型ブルームフィルタの提案と検索効率の評価(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- A-6-4 平均書き換え可能回数を指標としたIndex-less Indexedフラッシュ符号の改善(A-6.情報理論,一般セッション)
- A-6-3 主パス追跡内点法に基づくLP復号法の停止基準に関する検討(A-6.情報理論,一般セッション)
- IT2010-29 平均性能を指標とした改良型Index-less Indexedフラッシュ符号(フレッシュマンセッション,一般)
- 圧縮センシングにおける完全再現十分条件について
- B-7-80 新世代ネットワークサービス基盤としての仮想化技術のモデル化に関する一考察(B-7. 情報ネットワーク,一般セッション)
- A-6-10 反転候補集合を利用したビットフリッピング復号法の計算量削減手法(A-6.情報理論,一般セッション)
- 2元行列アンサンブルの見逃し誤り確率の平均誤り指数(LDPC符号,一般)
- A-6-2 複数の閾値を利用したGradient Descent-Bit Flipping復号法(A-6. 情報理論,一般セッション)
- LDPC符号のための勾配法に基づくビットフリップ復号法
- モバイルエージェント間ゴシップの移動計算量について
- 復号時符号長選択可能なLDPC符号の構成
- 差分写像法に基づくLDPC符号に適した反復復号法(LDPC符号,一般)
- ペナルティ関数を利用した内点LP復号法の改良(LDPC符号,一般)
- 観測に一様な誤差を生じるモデルでの自律分散ロボット群の一点収束について
- 偶数台の自律分散ロボット群に対するリング上での一点集合問題について
- 4台の自律分散ロボット群による正方形形成について
- 動的コンパスを持つロボット群の一点集合問題に対する許容変化量最適なアルゴリズム
- 故障したコンパスを持つ二台の自律分散ロボットに対する一点集合問題の可解性について
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 主パス追跡内点法に基づく最大分数距離計算法の改善(情報通信基礎サブソサイエティ合同研究会)
- 25pTD-13 2元行列アンサンブルの見逃し誤り確率の平均誤り指数(25pTD 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 極大クリーク分割に基づく自己安定クラスタリングアルゴリズム
- メッセージの確率的な消失を考慮した耐故障合意アルゴリズム
- AT-2-3 符号理論の観点から見た圧縮センシング(AT-2.リード・ソロモン符号50周年,チュートリアルセッション,ソサイエティ企画)
- A-6-1 ビット信頼度を用いたNormalized Min-Sum復号法の改良(A-6. 情報理論,一般セッション)
- 冗長行の検査行列への追加による Stopping Set 分布の改善について
- 相互無関係並列マシンにおける一般化多組織スケジューリング
- MSTに基づくSVMパス追跡を用いた多重多変量2標本検定による遺伝子群解析に関する一考察(IBIS2010(情報論的学習理論ワークショップ))
- BPとガウス消去法を組み合わせたLDPC符号の消失誤り訂正法
- コンパクトな表現を持つ2値センシング行列のランダム構成法について(一般セッション,フレッシュマンセッション,一般)
- 冗長行を用いた基本凸多面体の最小重み頂点の削除による分数距離の改善
- 2次元クラスタ消失に適したLDPC符号の構成法
- フェージング通信路における消失訂正を利用したq元LDPC符号の復号法
- 一次マルコフモデルを用いた適応型最小エネルギー符号化法
- 二つのエッジタイプを持つLDPC符号のエラーフロア改善手法
- 局所グラフカットに基づく高速かつ省メモリな画像セグメンテーション
- 2元行列アンサンブルの重み分布の共分散について
- 2.反復復号法の性能解析 : 密度発展法とその周辺(ターボ符号・LDPC符号と繰返し復号の理論)
- LP Decodable Permutation Codes based on Linearly Constrained Permutation Matrices (Frontiers in mathematical science through collaborations with other disciplines)
- 28aTD-6 疎行列に基づく圧縮センシング : キャビティ法による信号復元アルゴリズム(28aTD 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 二次計画法に基づく同期CDMAマルチユーザ検出アルゴリズム(スペクトル拡散技術)
- 線形制約が課された置換行列について
- 2次元磁気記録方式のための隣接ビット制約符号化方式について(信号処理及び一般)
- マルコフ動的ネットワークにおける通信効率のよいブロードキャストについて
- バースト誤り通信路に適した反復復号法(情報論的学習理論論文)
- AT-1-1 復号・復調問題への凸最適化アプローチ(AT-1.通信路符号化の最近の進歩,チュートリアルセッション,ソサイエティ企画)
- 平均性能を指標とした改良型Index-less Indexedフラッシュ符号(符号理論)
- ランダムグラフにおけるネットワーク信頼度の評価(フレッシュマンセッション,一般)
- 符号理論と理論計算機科学の接点 : グラフのカット問題を中心として(LDPC符号,一般)
- 分割画像のグラフカットに基づく高速かつ省メモリな画像前景抽出(画像認識,コンピュータビジョン,学生論文)
- 完全マッチング数え上げの高速な指数時間アルゴリズムについて (アルゴリズムと計算理論の新展開)
- 符号理論と完全マッチング計数問題の接点について
- Pure involution置換符号に基づく新しい置換符号について
- BT-1-1 よくわかるチャネル符号化 : LDPC符号を中心として(BT-1.よくわかるチャネル符号化と繰返し信号処理,チュートリアルセッション,ソサイエティ企画)
- Pure involution 置換符号に基づく新しい置換符号について
- 符号理論と完全マッチング計数問題の接点について
- MapReduce計算の並列複雑度について
- 多元LDPC符号に適したバースト誤り訂正アルゴリズム(符号理論)
- 疎グラフに基づくグループテスト方式に関する情報理論解析について
- 疎グラフに基づくグループテスト方式に関する情報理論解析について
- 17-3 2次元磁気記録方式におけるボロノイ離散グレインモデルの計算機実装について(第17部門 マルチメディアストレージ1)
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 2次元重み制約に適した反復コセット符号化法
- 有限サイズのInvertible Bloom Lookup Tablesの性能評価
- 2次元重み制約に適した反復コセット符号化法
- 2次元重み制約に適した反復コセット符号化法
- MapReduce計算の並列複雑度について(一般)
- 並列復号に適したプロトグラフ叉状結合型空間結合符号(誤り訂正符号,一般)