Back to Search
Start Over
Scaling matrices and counting the perfect matchings in graphs
- Source :
- Discrete Applied Mathematics, Discrete Applied Mathematics, 2022, 308, pp.130--146. ⟨10.1016/j.dam.2020.07.016⟩, Discrete Applied Mathematics, Elsevier, 2022, 2021, 308, pp.130--146
- Publication Year :
- 2022
- Publisher :
- HAL CCSD, 2022.
-
Abstract
- International audience; We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general undirected graphs. Our approach is based on assigning probabilities to edges, randomly selecting an edge to be in a perfect matching, and discarding edges that cannot be put in a perfect matching. The probabilities are chosen according to the entries in the doubly stochastically scaled version of the adjacency matrix of the given graph. The experimental analysis on random and real-life graphs shows improvements in the approximation over previous and similar methods from the literature.
- Subjects :
- matrices bistochastiques
ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory
Permanent approximation
algorithmes randomisés
randomized algorithms
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Sinkhorn-Knopp scaling
doubly stochastic matrices
permanent
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics, Discrete Applied Mathematics, 2022, 308, pp.130--146. ⟨10.1016/j.dam.2020.07.016⟩, Discrete Applied Mathematics, Elsevier, 2022, 2021, 308, pp.130--146
- Accession number :
- edsair.dedup.wf.001..999926a68722b86f6de44b8342478d47
- Full Text :
- https://doi.org/10.1016/j.dam.2020.07.016⟩