Scaling matrices and counting the perfect matchings in graphs

Dufossé, Fanny and Kaya, Kamer and Panagiotas, Ioannis and Uçar, Bora (2018) Scaling matrices and counting the perfect matchings in graphs. [Working Paper / Technical Report] Sabanci University ID:9161

PDF
RR-9161.pdf
Download (1MB)

Official URL: https://hal.inria.fr/hal-01743802/

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.

Item Type:	Working Paper / Technical Report
Subjects:	Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions:	Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences
Depositing User:	Kamer Kaya
Date Deposited:	31 Jul 2018 16:42
Last Modified:	26 Apr 2022 10:54
URI:	https://research.sabanciuniv.edu/id/eprint/35221

Actions (login required)

: View Item