Scaling matrices and counting the perfect matchings in graphs

Fanny Dufossé 1 Kamer Kaya 2 Ioannis Panagiotas 3 Bora Uçar 3
1 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01743802
Contributor : Equipe Roma <>
Submitted on : Tuesday, May 8, 2018 - 8:17:13 PM
Last modification on : Tuesday, April 2, 2019 - 2:52:14 AM
Long-term archiving on : Monday, September 24, 2018 - 3:09:32 PM

File

RR-9161.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01743802, version 5

Citation

Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Scaling matrices and counting the perfect matchings in graphs. [Research Report] RR-9161, Inria Grenoble Rhône-Alpes. 2018, pp.1-22. ⟨hal-01743802v5⟩

Share

Metrics

Record views

255

Files downloads

168