A weighted even factor algorithm
成果类型：
Article
署名作者：
Takazawa, Kenjiro
署名单位：
University of Tokyo; Kyoto University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0154-0
发表日期：
2008
页码：
223-237
关键词：
摘要：
An even factor in a digraph, introduced by Cunningham and Geelen (Vertex-disjoint dipaths and even dicircuits. manuscript, 2001), is a collection of vertex-disjoint dipaths and even dicycles, which generalizes a path-matching of Cunningham and Geelen (Combinatorica 17, 315-337, 1997). In a restricted class of digraphs, called odd-cycle-symmetric, Pap (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3509, pp. 66-80, Springer, Heidelberg, 2005) presented a combinatorial algorithm to find a maximum even factor. For odd-cycle-symmetric weighted digraphs, which are odd-cycle-symmetric digraphs accompanied by a weight vector satisfying a certain property, Kiraly and Makai (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3064, pp. 416-430, Springer, Heidelberg, 2004) provided a linear program that describes the maximum weight even factor problem, and proved the dual integrality. In this paper, we present a primal-dual algorithm to find a maximum weight even factor for an odd-cycle-symmetric weighted digraph. This algorithm is based on the weighted matching algorithm of Edmonds and the maximum even factor algorithm of Pap. The running time of the algorithm is O(n(3) m), where n and m are the numbers of the vertices and arcs, respectively, which is better than that of the existing algorithms for the special cases. The algorithm also gives a constructive proof for the dual integrality.