Algebraic Algorithms for Linear Matroid Parity Problems

DOI10.1145/2601066zbMath1333.05062OpenAlexW2170492169MaRDI QIDQ2799476

Lap Chi Lau, Ho Yee Cheung, Kai Man Leung

Publication date: 11 April 2016

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2601066

zbMATH Keywords

matroid parity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (14)

A cost-scaling algorithm for computing the degree of determinants ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Weighted matching with pair restrictions ⋮ Unnamed Item ⋮ Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ 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
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• An augmenting path algorithm for linear matroid parity
• Matroid matching and some applications
• Über die Maximalzahl kreuzungsfreier H-Wege
• The optimal path-matching problem
• The membership problem in jump systems
• On the graphic matroid parity problem
• The Schur complement and its applications
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• High-order lifting and integrality certification
• A fast algorithm for the path 2-packing problem
• Packing non-returning A-paths
• Packing non-returning \(A\)-paths algorithmically
• Matroid matching via mixed skew-symmetric matrices
• Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Some new results on node-capacitated packing of A-paths
• Algebraic Algorithms for Matching and Matroid Problems
• Weighted Bipartite Matching in Matrix Multiplication Time
• Connected Detachments of Graphs and Generalized Euler Trails
• Complexity of Matroid Property Algorithms
• Random pseudo-polynomial algorithms for exact matroid problems
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Fast matrix rank algorithms and applications
• Multiplying matrices faster than coppersmith-winograd
• Algorithms – ESA 2004
• Matrices and matroids for systems analysis

This page was built for publication: Algebraic Algorithms for Linear Matroid Parity Problems