Weighted linear matroid parity

DOI10.4230/LIPICS.ISAAC.2017.1MaRDI QIDQ5136215zbMATH OpenFDO

Authors Satoru Iwata

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2017.1

zbMATH Keywords

matchingmatroidPfaffianpolynomial-time algorithm

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Shortest disjoint S-paths via weighted linear matroid parity
• A Fast, Simpler Algorithm for the Matroid Parity Problem

Cites work

• A Fast, Simpler Algorithm for the Matroid Parity Problem
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for matching and matroid problems
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• 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
• scientific article; zbMATH DE number 3643026 (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?)
• Matching theory
• Matroid Intersection
• Matroid intersection algorithms
• Matroid matching and some applications
• Matroid matching via mixed skew-symmetric matrices
• Matroid matching: the power of local search
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• Minimum partition of a matroid into independent subsets
• On the Abstract Properties of Linear Dependence
• 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 linear delta-matroid parity problem
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(9)

• The linear delta-matroid parity problem
• Weighted matching with pair restrictions
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• Random pseudo-polynomial algorithms for exact matroid problems
• Shortest disjoint S-paths via weighted linear matroid parity
• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems

This page was built for publication: Weighted linear matroid parity

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