劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
スポンサーリンク
概要
- 論文の詳細を見る
有限集合 V と集合関数 ƒ : 2^V & Z (Zは整数値の集合) が与えれたとき, V上で多重グラフ G=(V, E) を構成し, G のカット関数 c_Gが任意の非空部分集合 X⊂V に対してƒ(X)+c_G(X)≥2を満たすようにする. 関数 f が交差劣モジュラ, 正モジュラであり, かつ三部不等式を満たすとき, 上記の性質を満たすグラフの中で辺数最小のものをO((T_ƒ+1)n^4log n) 時間で求めるアルゴリズムを与える. ここで, n=|V|, T_ƒ与えられたX⊂Vに対しƒ(X)の値を返す時間とする.
- 一般社団法人情報処理学会の論文
- 1999-01-27
著者
関連論文
- タンク繰りにおける経路探索法
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
- 動的交通流配分のネットワーク・モデル
- スケジューリングの理論
- 無向ネットワーク内の全ての最小カットを表すカクタス表現の構成について(グラフ理論(1))
- 部分定義論理関数のホーン拡張について
- オプションプライシングと凸計画問題の関係について(金融工学(3))
- 給油施設操業スケジューリング
- 1-D-8 紙管製造工程における1次元カッティングストック問題(離散アルゴリズム(3))
- ネットワークの辺連結度増加問題を解くアルゴリズムの計算機実験(グラフ理論(2))
- アルゴリズム研究会(研究会千夜一夜)
- 離散構造を紐解くグラフ連結度アルゴリズム(文献賞受賞招待講演)
- 1-F-2 時間依存距離付きネットワークにおける2地点間の最短路アルゴリズム(動的計画)
- 劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
- 辺連結度増加関数の計算法(ネットワーク(1))
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- Augmenting a (k-1)-Vertex-Connected Multigraph to an l-Edge-Connected and k-Vertex-Connected Multigraph
- Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
- Augmenting edge-connectivity and vertex-connectivity simultaneously
- 辺連結度,点連結度を同時に最適増大させる問題
- 機械式立体駐車場入出庫スケジューリング
- 機械式立体駐車場出庫スケジューリング
- 無向ネットワークの最小カットを求める実用的高速アルゴリズム(グラフ・ネットワーク)
- A Tight Upper Bound on the Number of Small Cuts in Undirected Networks
- Vehicle Scheduling on a Tree to Minimize Maximum Lateness(スケジューリング(2))
- リリースタイムとハンドリングタイムを考慮した木状経路における搬送スケジューリング(スケジューリング)
- 最近のアルゴリズムから : OR若手から一言(OR : 21世紀に向けて)
- 正理論関数の部分データに基づく正決定木の構成について(組み合わせ最適化(3))
- メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
- オイラー有向グラフにおける2本の辺素なパスの存在判定
- 最適化アルゴリズムの最近の動き
- 無向グラフにおけるk-辺分割問題の一般化について