首页|Scaling matrices and counting the perfect matchings in graphs
Scaling matrices and counting the perfect matchings in graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2020 Elsevier B.V.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 set 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.
Doubly stochastic matrixPerfect matchingPermanent
Dufosse F.、Kaya K.、Panagiotas I.、Ucar B.
展开 >
Univ. Grenoble Alpes Inria CNRS Grenoble INP LIG
Faculty of Engineering and Natural Sciences Sabanci University
ENS Lyon
Univ Lyon CNRS ENS de Lyon Inria université Claude-Bernard Lyon 1 LIP UMR 5668
NSTL
Elsevier
