An augmenting path algorithm for linear matroid parity

DOI10.1007/BF02579169zbMath0612.05018OpenAlexW2031297526MaRDI QIDQ1087880

Harold N. Gabow, Matthias F. M. Stallmann

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579169

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

RNC-approximation algorithms for the steiner problem ⋮ 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 ⋮ Boundary classes for graph problems involving non-local properties ⋮ Efficient optimal equation formulation in lumped power-conserving systems ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ The linear delta-matroid parity problem ⋮ An algorithm for weighted fractional matroid matching ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Weighted matching with pair restrictions ⋮ Structural properties of matroid matchings ⋮ Matroid matching with Dilworth truncation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Spanning trees of 3-uniform hypergraphs ⋮ Unnamed Item ⋮ Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Searching for a strong double tracing in a graph ⋮ Fractional matroid matchings ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On matroid parity and matching polytopes ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Matroid matching and some applications
• The dependence graph for bases in matroids
• Efficient algorithms for a family of matroid intersection problems
• Complexity of Matroid Property Algorithms
• On the Asymptotic Complexity of Matrix Multiplication
• Efficiency of a Good But Not Linear Set Union Algorithm
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Decomposing symmetric exchanges in matroid bases
• On the Abstract Properties of Linear Dependence
• Paths, Trees, and Flowers