A weighted independent even factor algorithm

• Takazawa, Kenjiro

Abstract

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.

Journal

• Mathematical Programming

  Mathematical Programming 132 (1-2), 261-276, 2012-04

  Springer and Mathematical Optimization Society

Keywords

• Independent even factor
• Combinatorial algorithm
• Dual integrality
• Nonbipartite matching
• Matroid intersection

Details

• CRID: 1050001335731818240
• NII Article ID: 120003988372
• NII Book ID: AA00295781
• ISSN: 00255610
• HANDLE: 2433/154867
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles