Dufossé, Fanny and Kaya, Kamer and Panagiotas, Ioannis and Uçar, Bora (2020) Scaling matrices and counting the perfect matchings in graphs. (Accepted)
There is a more recent version of this item available.
![[thumbnail of Open Access]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
PDF (Open Access)
1-s2.0-S0166218X20303620-main.pdf
Download (2MB)
Official URL: http://dx.doi.org/10.1016/j.dam.2020.07.016
Abstract
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 > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences > Basic Sciences > Mathematics Faculty of Engineering and Natural Sciences |
| Depositing User: | Kamer Kaya |
| Date Deposited: | 02 Sep 2021 18:22 |
| Last Modified: | 26 Apr 2022 10:26 |
| URI: | https://research.sabanciuniv.edu/id/eprint/41940 |
Available Versions of this Item
- Scaling matrices and counting the perfect matchings in graphs. (deposited 02 Sep 2021 18:22) [Currently Displayed]
Actions (login required)
- View Item