Scaling matrices and counting the perfect matchings in graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2022

Scaling matrices and counting the perfect matchings in graphs

Normalisation de matrice et dénombrement des couplages parfaits dans les graphes

Résumé

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.
Fichier principal
Vignette du fichier
dlpu22.pdf (1.58 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01743802 , version 1 (26-03-2018)
hal-01743802 , version 2 (27-03-2018)
hal-01743802 , version 3 (31-03-2018)
hal-01743802 , version 4 (08-04-2018)
hal-01743802 , version 5 (08-05-2018)
hal-01743802 , version 6 (28-12-2021)

Identifiants

Citer

Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Scaling matrices and counting the perfect matchings in graphs. Discrete Applied Mathematics, 2022, 308, pp.130--146. ⟨10.1016/j.dam.2020.07.016⟩. ⟨hal-01743802v6⟩
473 Consultations
847 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More