ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
スポンサーリンク
概要
- 論文の詳細を見る
We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
Boros E
Rutcor Rutgers University
-
Boros Endre
Rutgers University
-
Boros Endre
Rutgers Center For Operations Research Rutgers University
-
Boros Endre
ラトガース大学ラトコー研究所
-
牧野 和久
University Of Tokyo
-
Gurvich V
Rutcor Rutgers University
-
Khachiyan L
Department Of Computer Science Rutgers University
-
Borys Konrad
Rutgers University
-
Elbassioni Khaled
Max-Planck-Institut fur Informatik
-
Gurvich Vladimir
Rutgers University
-
Makino Kazuhisa
University of Tokyo
-
Gurivich Vladimir
Rutcor Rutgers University
関連論文
- 双対制限された列挙問題 : 離散分布に対する交差不等式とその応用
- ラミナー被覆制約を持つ単調凹関数最小化問題
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks
- ルール生成に必要なデータ量に関するランダム性に基づいた解析
- 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
- 閾グラフの最小辺ランキング全域木について
- A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns
- Transformations on Regular Non-Dominated Coteries and Their Application (Algorithm Engineering as a New Paradigm)
- 正則コテリの効率的な列挙について
- 不完全データの論理的解析
- 不完全例題に対するプール的解析
- Extensions of Partially Defined Boolean Functions with Missing Data
- Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions
- 双対制限されたハイパーグラフ:部分横断と多重横断の列挙について
- 単調線形システムにおけるすべての極小な整数解について
- ハイパーグラフの重み付き横断
- フロー制約を持つソース配置問題に対する近似アルゴリズム
- 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
- 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)
- 単調双対化問題とハイパーグラフ横断列挙問題に対する新しい結果について
- ホーン理論とq-ホーン理論の極小関数従属性の推定について
- ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(the 50th Anniversary of the Operations Research Society of Japan)
- ハイパーグラフの重み付き横断
- 無向ネットワーク中のソース配置問題の強NP困難性とその近似アルゴリズム(組合せ最適化(5))
- LA-002 無向ネットワーク中のソース配置問題に対する近似アルゴリズム(A. モデル・アルゴリズム・プログラミング)
- ラミナー被覆制約を持つ単調凹関数最小化問題(グラフ・ネットワーク)
- O(log n)項単調論理和標準形の効率的な双対化について
- 部分定義ブール関数のダブルホーン拡張および限定ホーン拡張
- ホーン理論と推論問題(理論計算機科学の最新動向)
- データの論理的解析とブール関数
- 1-C-8 キャンセルコスト付きオンラインナップサック問題(離散最適化(1))
- 2-F-4 オンラインナップサック問題に対する乱択アルゴリズム(離散最適化(5))