An augmenting path algorithm for linear matroid parity

DOI10.1007/BF02579169zbMATH Open0612.05018OpenAlexW2031297526MaRDI QIDQ1087880FDOQ1087880

Authors: 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

Recommendations

• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for linear matroid parity problems
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• The linear delta-matroid parity problem
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Constructive algorithm for path-width of matroids
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (32)

• Packing \(A\)-paths in group-labelled graphs via linear matroid parity
• Title not available (Why is that?)
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• Title not available (Why is that?)
• Algebraic algorithms for linear matroid parity problems
• Searching for a strong double tracing in a graph
• Weighted linear matroid parity
• An algorithm for weighted fractional matroid matching
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Spanning trees of 3-uniform hypergraphs
• Strict matching matroids and matroid algorithms
• The linear delta-matroid parity problem
• Efficient optimal equation formulation in lumped power-conserving systems
• Matroid matching via mixed skew-symmetric matrices
• A weighted linear matroid parity algorithm
• Matroid matching with Dilworth truncation
• Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
• Fractional matroid matchings
• Boundary classes for graph problems involving non-local properties
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Weighted matching with pair restrictions
• Berge's theorem for the maximum charge problem
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• On matroid parity and matching polytopes
• RNC-approximation algorithms for the steiner problem
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Structural properties of matroid matchings
• A deterministic PTAS for the commutative rank of matrix spaces
• On the graphic matroid parity problem
• Minimally connected \(r\)-uniform hypergraphs
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• Title not available (Why is that?)

This page was built for publication: An augmenting path algorithm for linear matroid parity

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