Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
DOI10.1137/21M1421751zbMATH Open1497.05028OpenAlexW4294771615MaRDI QIDQ5866449FDOQ5866449
Authors: Kazuki Matoya, Taihei Oki 
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
Recommendations
matchingPfaffian orientationPfaffianarborescencematrix-tree theoremcounting algorithmlinear matroid intersectionlinear matroid parityspanning hypertree\(\mathcal{S}\)-paths\(S\)-\(T\) pathsregular delta-matroid
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial optimization (90C27) 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 aspects of matroids and geometric lattices (05B35)
Cites Work
- Title not available (Why is that?)
- Matching theory
- Binomial determinants, paths, and hook length formulae
- A characterization of convertible (0,1)-matrices
- Permanents, Pfaffian orientations, and even directed circuits
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- Dimer problem in statistical mechanics-an exact result
- Title not available (Why is that?)
- The complexity of computing the permanent
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Title not available (Why is that?)
- Connections in combinatorial optimization
- Title not available (Why is that?)
- Algebraic algorithms for matching and matroid problems
- Title not available (Why is that?)
- On the Vector Representations of Induced Matroids
- Title not available (Why is that?)
- Matroid matching and some applications
- Über die Maximalzahl kreuzungsfreier H-Wege
- A weighted matroid intersection algorithm
- A weighted linear matroid parity algorithm
- Minor summation formula of pfaffians
- Title not available (Why is that?)
- Menger's theorem for matroids
- Coverings and delta-coverings
- Title not available (Why is that?)
- Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
- An augmenting path algorithm for linear matroid parity
- Principally unimodular skew-symmetric matrices
- Title not available (Why is that?)
- Efficient theoretic and practical algorithms for linear matroid intersection problems
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Computing the Degree of Determinants via Combinatorial Relaxation
- Note on the Pfaffian matrix-tree theorem
- Shortest disjoint \(S\)-paths via weighted linear matroid parity
- Spanning trees of 3-uniform hypergraphs
- Algebraic algorithms for linear matroid parity problems
- A Fast, Simpler Algorithm for the Matroid Parity Problem
- Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
- Counting bases of representable matroids
- The complexity of computing the Tutte polynomial on transversal matroids
- Matroid matching via mixed skew-symmetric matrices
- Matrices and matroids for systems analysis
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- Complexity Dichotomies for Counting Problems
Cited In (5)
This page was built for publication: Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5866449)
