Computing the Partition Function for Perfect Matchings in a Hypergraph
From MaRDI portal
Publication:3103630
DOI10.1017/S0963548311000435zbMath1234.05181arXiv1009.2397OpenAlexW2139974605MaRDI QIDQ3103630
Alex Samorodnitsky, Alexander I. Barvinok
Publication date: 8 December 2011
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.2397
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Computing the permanent of (some) complex matrices, Hafnians, perfect matchings and Gaussian matrices, Permanents of multidimensional matrices: Properties and applications, An efficient tree decomposition method for permanents and mixed discriminants, On testing Hamiltonicity of graphs, Approximating permanents and hafnians, Spectral Analysis of Matrix Scaling and Operator Scaling
Cites Work
- Exponentially many perfect matchings in cubic graphs
- The complexity of computing the permanent
- Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums
- The solution of van der Waerden's problem for permanents
- The number of \(t\)-wise balanced designs
- A short proof of Minc's conjecture
- Permanents of d-dimensional matrices
- Concentration of permanent estimators for certain large matrices.
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Concentration of Random Determinants and Permanent Estimators
- New permanental upper bounds for nonnegative matrices
- New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
