Live briefing
Everything about Matroid intersection
Shared independent set of two matroids
In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in graph theory and combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Matroid intersectionA 5-minute orientation
- Skim a recent paper: Hilbert–Poincaré series of matroid Chow rings and intersection cohomologyInfluential work since 2022
- Pick up a classic book: Algebraic, extremal, and metric combinatorics, 1986The most-reprinted book on the subject
- Read the landmark paper: A weighted matroid intersection algorithmCited 131 times
- Go sideways: Matroid parity problemA closely related topic
- Go sideways: Weighted matroidA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A weighted matroid intersection algorithm
Matroid intersection algorithms
Improved Bounds for Matroid Partition and Intersection Algorithms
Efficient algorithms for a family of matroid intersection problems
The intersection of a matroid and a simplicial complex
Valuated Matroid Intersection I: Optimality Criteria
Budgeted matching and budgeted matroid intersection via the gasoline puzzle
Valuated Matroid Intersection II: Algorithms
🆕 Influential since 2022
Hilbert–Poincaré series of matroid Chow rings and intersection cohomology
On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
Matroid Intersection under Restricted Oracles
Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
📚 Books worth reading
Algebraic, extremal, and metric combinatorics, 1986M. Deza · 1988
The Travelling Salesman Problem and Its VariationsGregory Gutin · 2002
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Matroid parity problem In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid, a structure…
- Weighted matroid In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with a function that assigns a weight to each element. Formally, let…
- Matroid oracle In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure…
- Matroid partitioning Matroid partitioning is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms. Its goal is to partition…
- Matching (graph theory) In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In…
- Independent set (graph theory) In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a…
- Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and…
- Kőnig's theorem (graph theory) In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem…