Algebraic Algorithms for Matching and Matroid Problems
From MaRDI portal
Publication:3558018
DOI10.1137/070684008zbMath1231.05214OpenAlexW2023810039MaRDI QIDQ3558018
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/52443
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (20)
Fair matchings and related problems ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation ⋮ Body-and-cad geometric constraint systems ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ On a weighted linear matroid intersection algorithm by deg-det computation ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation ⋮ Greedy matching: guarantees and limitations ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Faster Algorithms for Semi-Matching Problems ⋮ Even factors, jump systems, and discrete convexity ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Unnamed Item ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Unnamed Item ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
This page was built for publication: Algebraic Algorithms for Matching and Matroid Problems