A weighted independent even factor algorithm
スポンサーリンク
概要
- 論文の詳細を見る
An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n [3] γ + n [6] m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n [4] γ + n [5]) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.
論文 | ランダム
- 幸田露伴『風流仏』考(下) : 「珠運」構想背景と狩野芳崖をめぐって
- 幸田露伴『風流佛』考(上) : 「珠運」構想背景と狩野芳崖をめぐって
- 幸田露伴『風流佛』考 : 「発端 如是我聞」と「團圓 諸法実相」をめぐっての西欧的,キリスト教的視点からの考察
- 幸田露伴『露團々』考 : 『露團々』の風流観をめぐって
- 幸田露伴「露團々」考 : 露伴とキリスト教の関係と,「露團々」の愉快観,恋愛観の根底にあるキリスト教的思考の考察