Pfaffian pairs and parities: counting on linear matroid intersection and parity problems

DOI10.1007/978-3-030-73879-2_16zbMath1482.90231arXiv1912.00620OpenAlexW3164586374MaRDI QIDQ2061881

Taihei Oki, Kazuki Matoya

Publication date: 21 December 2021

Full work available at URL: https://arxiv.org/abs/1912.00620

zbMATH Keywords

matchingPfaffian orientationPfaffianmatrix-tree theoremcounting algorithm\( \mathcal{S} \)-pathlinear matroid intersectionlinear matroid parity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• 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
• 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
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• The complexity of computing the Tutte polynomial on transversal matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• 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
• Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
• 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
• 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
• On the Vector Representations of Induced Matroids