Abstract | ||
---|---|---|
In this note, we study a constrained independent set problem for matroids. The problem can be regarded as an ordered version of the matroid parity problem. By a reduction of this problem to matroid intersection, we prove a min-max formula. We show how earlier results of Hefner and Kleinschmidt on the so-called MS-matchings fit in our framework. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/S0167-6377(03)00063-4 | Oper. Res. Lett. |
Keywords | Field | DocType |
ms matchings,matroid parity,matroid intersection,matroid parity problem,independent set problem,so-called ms-matchings,min-max formula,earlier result,independent set | Matroid,Discrete mathematics,Combinatorics,Matroid intersection,Oriented matroid,Matroid partitioning,Independent set,Graphic matroid,Weighted matroid,Parity problem,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 1 | Operations Research Letters |
Citations | PageRank | References |
2 | 0.40 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tamás Fleiner | 1 | 241 | 27.45 |
András Frank | 2 | 753 | 163.71 |
Satoru Iwata | 3 | 759 | 70.03 |