Scaling matrices and counting the perfect matchings in graphs

Dufossé, Fanny and Kaya, Kamer and Panagiotas, Ioannis and Uçar, Bora (2022) Scaling matrices and counting the perfect matchings in graphs. Discrete Applied Mathematics (SI), 308 . pp. 130-146. ISSN 0166-218X (Print) 1872-6771 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


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.
Item Type: Article
Uncontrolled Keywords: Doubly stochastic matrix; Perfect matching; Permanent
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 31 Aug 2022 21:01
Last Modified: 31 Aug 2022 21:01

Available Versions of this Item

Actions (login required)

View Item
View Item