Back to Search Start Over

Scaling matrices and counting the perfect matchings in graphs

Authors :
Dufossé, Fanny
Kaya, Kamer
Panagiotas, Ioannis
Uçar, Bora
Data Aware Large Scale Computing (DATAMOVE )
Inria Grenoble - Rhône-Alpes
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG )
Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])
Faculty of Engineering and Natural Sciences (Sabanci University)
Sabanci University [Istanbul]
Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP)
Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL)
Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)
Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Inria Grenoble Rhône-Alpes
Source :
[Research Report] RR-9161, Inria Grenoble Rhône-Alpes. 2018, pp.1-22
Publication Year :
2018
Publisher :
HAL CCSD, 2018.

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.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.

Subjects

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

Details

Language :
English
Database :
OpenAIRE
Journal :
[Research Report] RR-9161, Inria Grenoble Rhône-Alpes. 2018, pp.1-22
Accession number :
edsair.od.......212..69bce2a3bac3ecc5cbb1b2469b3740d2

Tools

Authors Abstract Subjects Details