Scaling matrices and counting the perfect matchings in graphs
DOI10.1016/j.dam.2020.07.016zbMath1490.05216OpenAlexW2794797213MaRDI QIDQ2064289
Bora Uçar, Kamer Kaya, Ioannis Panagiotas, Fanny Dufossé
Publication date: 5 January 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01743802v6/file/dlpu22.pdf
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- The complexity of computing the permanent
- Matching theory
- Approximating the permanent via importance sampling with application to the dimer covering problem
- A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
- On the complexity of nonnegative-matrix scaling
- On counting perfect matchings in general graphs
- Concerning nonnegative matrices and doubly stochastic matrices
- A fast algorithm for matrix balancing
- The statistics of dimers on a lattice
- A Symmetry Preserving Algorithm for Matrix Scaling
- The university of Florida sparse matrix collection
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Coverings of Bipartite Graphs
- Approximating the permanent: A simple approach
- Computing the block triangular form of a sparse matrix
- Dimer problem in statistical mechanics-an exact result
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
This page was built for publication: Scaling matrices and counting the perfect matchings in graphs
