An intersection theorem for supermatroids

DOI10.1016/0095-8956(90)90070-GMaRDI QIDQ803140zbMATH OpenFDO

Authors Éva Tardos

Publication date 1990

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(90)90070-G

zbMATH Keywords

distributive supermatroidsgreedoidsmatroid intersection theoremmatroid matching problempolymatroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

The author generalizes the matroid intersection theorem to distributive supermatroids, a structure that extends the matroid to the partially ordered ground set. Distributive supermatroids are special cases of both supermatroids and greedoids, and they generalize polymatroids. This is the first good characterization proved for the intersection problem of an independence system where the ground set is partially ordered. The two partially ordered distributive supermatroids are defined on the same partially ordered set. The author also shows that the problem of finding the maximum common independent set of two supermatroids defined of different partially ordered sets contains the matroid matching problem as a special case.

Recommendations

• scientific article; zbMATH DE number 3970769
• scientific article; zbMATH DE number 3906513
• Weakly submodular rank functions, supermatroids, and the flat lattice of a distributive super\-matroid
• Independent set axioms, base axioms and circuit axioms of supermatroids
• scientific article; zbMATH DE number 3908450

Cites work

• Geometries on partially ordered sets
• scientific article; zbMATH DE number 3871387 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Matching theory
• Structural properties of greedoids

Cited in

(15)

• A general model for matroids and the greedy algorithm
• Generalized matroids based on three-way decision models
• Base axioms of modular supermatroids
• Rank axiom of modular supermatroids: a connection with directional DR submodular functions
• Weakly submodular rank functions, supermatroids, and the flat lattice of a distributive super\-matroid
• scientific article; zbMATH DE number 3841891 (Why is no real title available?)
• scientific article; zbMATH DE number 3908450 (Why is no real title available?)
• scientific article; zbMATH DE number 3970767 (Why is no real title available?)
• scientific article; zbMATH DE number 3970769 (Why is no real title available?)
• Independent set axioms, base axioms and circuit axioms of supermatroids
• Toward an Automatic Approach to Greedy Algorithms
• Matroids on convex geometries: subclasses, operations, and optimization
• Poset matching---a distributive analog of independent matching
• Matroids on convex geometries (cg-matroids)
• Rank functions of strict cg-matroids

This page was built for publication: An intersection theorem for supermatroids

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