Matroid matching and some applications

DOI10.1016/0095-8956(80)90066-0zbMath0444.05031OpenAlexW2000743971MaRDI QIDQ1144584

Publication date: 1980

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(80)90066-0

zbMATH Keywords

hypergraph matching polynomial algorithm matroid rigid structure polymatroid

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40)

Related Items

On Finding Hamiltonian Cycles in Barnette Graphs, Randomized algorithms in combinatorial optimization: A survey, Approximating Bounded Degree Deletion via Matroid Matching, An augmenting path algorithm for linear matroid parity, Optimization problems with color-induced budget constraints, Packing non-zero $A$-paths via matroid matching, Free multiflows in bidirected and skew-symmetric graphs, Pseudomatroids, The membership problem in jump systems, Source location with rigidity and tree packing requirements, Singular spaces of matrices and their application in combinatorics, Multiflows and disjoint paths of minimum total cost, Boundary classes for graph problems involving non-local properties, Simultaneous feedback edge set: a parameterized perspective, Slider-pinning rigidity: a Maxwell-Laman-type theorem, The delta-sum of matching delta-matroids, On enumerating monomials and other combinatorial structures by polynomial interpolation, Coverings and delta-coverings, Finding Maximum Edge-Disjoint Paths Between Multiple Terminals, Feedback vertex set reconfiguration in planar graphs, Iterated parallel union of matroids, Optimal general factor problem and jump system intersection, The work of June Huh, On the graphic matroid parity problem, The linear delta-matroid parity problem, Edge deletion to tree-like graph classes, Generating functions and counting formulas for spanning trees and forests in hypergraphs, Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three, Matroid Intersection under Restricted Oracles, A randomized polynomial kernel for subset feedback vertex set, Degree conditions for the existence of vertex-disjoint cycles and paths: a survey, Recent Developments in Discrete Convex Analysis, An algorithm for weighted fractional matroid matching, Tree metrics and edge-disjoint $S$-paths, Finite prime-field characteristic sets for planar configurations, A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem, An appraisal of computational complexity for operations researchers, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, A Weighted Linear Matroid Parity Algorithm, Optimal Matching Forests and Valuated Delta-Matroids, An algorithm for packing non-zero $A$-paths in group-labelled graphs, Structural properties of matroid matchings, Matroid matching with Dilworth truncation, Packing non-returning $A$-paths algorithmically, On Some Problems in the Design of Plane Skeletal Structures, Fanout limitations on constraint systems, Unnamed Item, A fast algorithm for the path 2-packing problem, The parity problem of polymatroids without double circuits, Unnamed Item, On some combinatorial properties of algebraic matroids, Spanning trees of 3-uniform hypergraphs, A unifying approach to descriptive geometry and mechanisms, Combinatorial auctions with decreasing marginal utilities, Optimal matroid partitioning problems, Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity, Algebraic Algorithms for Linear Matroid Parity Problems, A polynomial kernel for distance-hereditary vertex deletion, The Complexity of Acyclic Subhypergraph Problems, Unnamed Item, Solving the linear matroid parity problem as a sequence of matroid intersection problems, Pfaffian pairs and parities: counting on linear matroid intersection and parity problems, On cycles through prescribed vertices in weakly separable graphs, Unnamed Item, Unnamed Item, A parameterized view on matroid optimization problems, On matroid parity and matching polytopes, The $d$-dimensional rigidity matroid of sparse graphs, A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection, A short proof of Mader's $\mathcal S$-paths theorem, A linear programming formulation of Mader's edge-disjoint paths problem, Packings and 2-packings of A-paths, Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

Cites Work