最大リーフ全域木問題の上界値計算について
スポンサーリンク
概要
- 論文の詳細を見る
最大リーフ全域木問題とは, 連結無向グラフGの全域木の中で, リーフ(次数1の頂点)数が最大のものを求める問題である.この問題はNP-困難であり, いくつかの近似解法, すなわち下界値計算が提案されている.これに対し, 本稿では, 上界値計算に関連した議論を行う.まず, この問題の0-1整数計画問題としての定式化を2通り与える.次に, 各定式化について, 定式化に用いた不等式が, 実行可能解集合の凸包として定義される多面体の極大面を定める必要十分条件を与える.最後に, 緩和問題について触れる.
- 一般社団法人情報処理学会の論文
- 1998-09-16
著者
関連論文
- A Cutting Plane Approach to Hub Network Design Problems
- A Branch-and-Bound Algorithm for a Class of Three-machine Flowshop Problems (Essays in Commemoration of the Fortieth Anniversary of Department of Management Science)
- 総滞留時間最小化1機械スケジューリング問題に対する優越テストについて(スケジューリング)
- 小売業におけるサービスタイム開始の判断基準に関する一考察(在庫管理)
- 階層的3機械フローショップ問題(スケジューリング)
- 最大リーフ全域木問題に対する厳密解法(グラフ・ネットワーク(2))
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))
- 整数計画問題に対する分枝カット法とカットの理論(OR研究の最前線)
- 半正定値計画とその応用 : 第3回半正定値計画による緩和(2)
- 半正定値計画とその応用 : 第2回半正定植計画による緩和(1)
- 一般化安定集合問題に対する半正定値計画緩和
- 混合整数計画問題に対する分枝カット法
- 最大リーフ全域木問題の上界値計算について