全域的でない枝素な有向木族の特徴付け
スポンサーリンク
概要
- 論文の詳細を見る
最近,神山・加藤・瀧澤によって,枝素な全域ブランチングに関するEdmondsの定理を真に拡張する枝素な有向木の詰め込みに関する新しい定理が示された.本文で,神山・加藤・瀧澤の定理における到達可能性の条件の本質的な役割を明らかにし,彼らの定理をさらに真に拡張した定理を示す.この拡張において重要な役割は,到達可能性ではなくて,張るべき点集合の凸性である.
- 一般社団法人情報処理学会の論文
- 2008-09-05
著者
関連論文
- ラミナー被覆制約を持つ単調凹関数最小化問題
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks
- 凸性を有する有向グラフ上の独立有向木族の特徴付け
- パラメトリックな劣モジュラ交わり問題の構造理論 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- DS-1-5 パラメトリックな劣モジュラ交わり問題の構造理論(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- フロー制約を持つソース配置問題に対する近似アルゴリズム
- Pairwise Stability in a General Two-Sided Matching Model Based on Discrete Concave Utility Functions
- 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
- 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)
- 離散最適化における未解決問題(次世代ORのオープン・プロブレム)
- LA-002 無向ネットワーク中のソース配置問題に対する近似アルゴリズム(A. モデル・アルゴリズム・プログラミング)
- 全域的でない枝素な有向木族の特徴付け
- マトロイドと劣モジュラ関数(学生/教養のページ)
- 組合せ最適化(定評ある教科書・古典的書籍)