Algebraic algorithms for matching and matroid problems

DOI10.1137/070684008MaRDI QIDQ3558018zbMATH OpenOpenAlexFDO

Authors Nicholas J. A. Harvey

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

zbMATH Keywords

algebraic algorithmsfast matrix multiplicationmatroid intersectionnonbipartite matching

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for linear matroid parity problems
• An algebraic algorithm for weighted linear matroid intersection
• Algebraic Graph Algorithms
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems

Cited in

(29)

• An algebraic matching algorithm
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• On a weighted linear matroid intersection algorithm by deg-det computation
• Exact and approximation algorithms for weighted matroid intersection
• Bi-criteria and approximation algorithms for restricted matchings
• Even factors, jump systems, and discrete convexity
• Fair matchings and related problems
• Algebraic algorithms for linear matroid parity problems
• Faster algorithms for semi-matching problems
• The Medusa algorithm for polynomial matings
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Linear-time approximation for maximum weight matching
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• Algebraic Graph Algorithms
• Body-and-cad geometric constraint systems
• A simple reduction from maximum weight matching to maximum cardinality matching
• Greedy matching: guarantees and limitations
• Weighted linear matroid parity
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• A scaling algorithm for maximum weight matching in bipartite graphs
• Algorithms for weighted matching generalizations. I: Bipartite graphs, b-matching, and unweighted f-factors
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Fast algorithms via dynamic-oracle matroids
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• Finding spanning trees with perfect matchings
• Faster algorithms on linear delta-matroids

This page was built for publication: Algebraic algorithms for matching and matroid problems

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