Counting the number of perfect matchings, and generalized decision trees
From MaRDI portal
Publication:2044128
DOI10.1134/S0032946021020046zbMath1469.05081OpenAlexW3178087926MaRDI QIDQ2044128
Publication date: 4 August 2021
Published in: Problems of Information Transmission (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0032946021020046
Trees (05C05) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Odd \(K_{3,3}\) subdivisions in bipartite graphs
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- The complexity of computing the permanent
- Boolean function complexity. Advances and frontiers.
- On the parity complexity measures of Boolean functions
- On the theory of Pfaffian orientations. I: Perfect matchings and permanents
- Matchings in graphs on non-orientable surfaces
- A characterization of convertible (0,1)-matrices
- Permanents, Pfaffian orientations, and even directed circuits
- On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
- Lower Bounds in Communication Complexity
- Composition Theorems in Communication Complexity
- Matrix Analysis
- Structure of Protocols for XOR Functions
- Determinant: Old Algorithms, New Insights
- Communication Complexity
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Analysis of Boolean Functions
This page was built for publication: Counting the number of perfect matchings, and generalized decision trees
