A weighted linear matroid parity algorithm

DOI10.1137/17M1141709MaRDI QIDQ5149751zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Yusuke Kobayashi

Publication date 8 February 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1141709

zbMATH Keywords

matchingpolynomial-time algorithmPfaffianprimal-dual approachlinear matroid parity

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• A weighted linear matroid parity algorithm
• Weighted linear matroid parity
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Algebraic algorithms for linear matroid parity problems

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3703542 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for matching and matroid problems
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• An algorithm for weighted fractional matroid matching
• An augmenting path algorithm for linear matroid parity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Computing the Degree of Determinants via Combinatorial Relaxation
• Fractional matroid matchings
• Matching theory
• Matrices and matroids for systems analysis
• Matroid Intersection
• Matroid intersection algorithms
• Matroid matching and some applications
• Matroid matching in pseudomodular lattices
• Matroid matching via mixed skew-symmetric matrices
• Matroid matching: the power of local search
• Maximum matching and a polyhedron with 0,1-vertices
• On some combinatorial properties of algebraic matroids
• Packing A-paths in group-labelled graphs via linear matroid parity
• Packing non-returning A-paths
• Packing non-zero \(A\)-paths in group-labelled graphs
• Packing non-zero \(A\)-paths via matroid matching
• Paths, Trees, and Flowers
• Random pseudo-polynomial algorithms for exact matroid problems
• Shortest disjoint S-paths via weighted linear matroid parity
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Steiner tree approximation via iterative randomized rounding
• The Factorization of Linear Graphs
• The linear delta-matroid parity problem
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(28)

• scientific article; zbMATH DE number 11347 (Why is no real title available?)
• Approximation algorithm for solving the 1-line Steiner tree problem with minimum number of Steiner points
• Algebraic algorithms for linear matroid parity problems
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• Weighted linear matroid parity
• An algorithm for weighted fractional matroid matching
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• The linear delta-matroid parity problem
• A weighted linear matroid parity algorithm
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Algebraic algorithms for linear matroid parity problems
• An improved algorithm for finding maximum outerplanar subgraphs
• A cost-scaling algorithm for computing the degree of determinants
• A weighted independent even factor algorithm
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Shortest disjoint S-paths via weighted linear matroid parity
• On a weighted linear matroid intersection algorithm by deg-det computation
• Weighted matching with pair restrictions
• An augmenting path algorithm for linear matroid parity
• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
• Random pseudo-polynomial algorithms for exact matroid problems
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• Combination algorithms for Steiner tree variants
• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2 2 submatrices
• Algorithm for constraint partial inverse matroid problem with weight increase forbidden

This page was built for publication: A weighted linear matroid parity algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149751)