Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
DOI10.1137/21M1421751zbMath1497.05028OpenAlexW4294771615MaRDI QIDQ5866449
Publication date: 21 September 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1421751
matchingPfaffian orientationPfaffianmatrix-tree theoremarborescencecounting algorithmlinear matroid intersectionlinear matroid parityspanning hypertree\(\mathcal{S}\)-paths\(S\)-\(T\) pathsregular delta-matroid
Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matroids and geometric lattices (05B35)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Spanning trees of 3-uniform hypergraphs
- Binomial determinants, paths, and hook length formulae
- An augmenting path algorithm for linear matroid parity
- Matching theory
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Matroid matching and some applications
- Über die Maximalzahl kreuzungsfreier H-Wege
- Principally unimodular skew-symmetric matrices
- Efficient theoretic and practical algorithms for linear matroid intersection problems
- The complexity of computing the Tutte polynomial on transversal matroids
- A characterization of convertible (0,1)-matrices
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Note on the Pfaffian matrix-tree theorem
- Counting bases of representable matroids
- Permanents, Pfaffian orientations, and even directed circuits
- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- Matroid matching via mixed skew-symmetric matrices
- Algebraic Algorithms for Linear Matroid Parity Problems
- The statistics of dimers on a lattice
- A Fast, Simpler Algorithm for the Matroid Parity Problem
- Algebraic Algorithms for Matching and Matroid Problems
- A weighted matroid intersection algorithm
- Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
- Complexity Dichotomies for Counting Problems
- Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity
- Computing the Degree of Determinants via Combinatorial Relaxation
- Minor summation formula of pfaffians
- A weighted linear matroid parity algorithm
- Coverings and delta-coverings
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- Dimer problem in statistical mechanics-an exact result
- Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
- Menger's theorem for matroids
- On the Vector Representations of Induced Matroids
- Matrices and matroids for systems analysis
