A weighted independent even factor algorithm
This paper deals with the weighted independent even factor problem (WIEFP) in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via a valuated matroid intersection. This paper presents a primal-dual algorithm. The contribution of this paper is a combinatorial algorithm for the WIEFP in odd-cycle symmetric weighted digraphs. This algorithm commonly extends classical algorithms for the weighted matching and weighted matroid intersection problems, and works directly on the WIEFP. The time complexity of the algorithm is \(O(n^{4}\gamma+n^{5}).\) The algorithm finds an integer optimal solution for a linear program corresponding to the WIEFP, and simultaneously finds an integer optimal solution for the dual program if the weight is integer. Thus, it provides a new dual integrality theorem which commonly extends those for matching, matroid intersection, independent path-matching and even factors.
- A weighted even factor algorithm
- The Weighted Averages Algorithm Revisited
- scientific article; zbMATH DE number 5888314
- scientific article; zbMATH DE number 7404279
- scientific article; zbMATH DE number 67638
- The weighted majority algorithm
- A weighted linear matroid parity algorithm
- A weighted linear matroid parity algorithm
- A faster algorithm for the maximum even factor problem
- An explicit factorization algorithm
- A Gallai–Edmonds‐type structure theorem for path‐matchings
- A weighted even factor algorithm
- Combinatorial algorithms for matchings, even factors and square-free 2-factors
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Even factors, jump systems, and discrete convexity
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3637616 (Why is no real title available?)
- scientific article; zbMATH DE number 2086910 (Why is no real title available?)
- scientific article; zbMATH DE number 5691235 (Why is no real title available?)
- Integer Programming and Combinatorial Optimization
- M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
- Matching, matroids, and extensions
- Matroid Intersection
- Matroid intersection algorithms
- Maximum matching and a polyhedron with 0,1-vertices
- Note on the path‐matching formula
- On the maximum even factor in weakly symmetric graphs
- Paths, Trees, and Flowers
- The Independent Even Factor Problem
- The optimal path-matching problem
- Valuated Matroid Intersection I: Optimality Criteria
- Valuated Matroid Intersection II: Algorithms
- The weighted majority algorithm
- Even factors, jump systems, and discrete convexity
- scientific article; zbMATH DE number 5888314 (Why is no real title available?)
- A Combinatorial Algorithm to Find a Maximum Even Factor
- scientific article; zbMATH DE number 11347 (Why is no real title available?)
- Valuated Matroid Intersection II: Algorithms
- Optimal matching forests and valuated delta-matroids
- Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
- Integer Programming and Combinatorial Optimization
- A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
- Jebelean-Weber's algorithm without spurious factors
- A weighted even factor algorithm
This page was built for publication: A weighted independent even factor algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429469)
