Scaling matrices and counting the perfect matchings in graphs

被引：2
|
作者：
Dufosse, Fanny [1 ]
Kaya, Kamer [2 ]
Panagiotas, Ioannis [3 ]
Ucar, Bora [4 ]
机构：
[1] Univ Grenoble Alpes, CNRS, INRIA, Grenoble, France
[2] Sabanci Univ, Fac Engn & Nat Sci, Istanbul, Turkey
[3] ENS Lyon, Lyon, France
[4] Univ Lyon, Univ Claude Bernard Lyon 1, CNRS, ENS Lyon, F-69007 Lyon, France
来源：
DISCRETE APPLIED MATHEMATICS | 2022年 / 308卷
关键词：
Permanent; Perfect matching; Doubly stochastic matrix; ALGORITHM; PERMANENT;
D O I：
10.1016/j.dam.2020.07.016
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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. (c) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：130 / 146
页数：17
相关论文
共 50 条
  • [1] On Counting Perfect Matchings in General Graphs
    Stefankovic, Daniel
    Vigoda, Eric
    Wilmes, John
    LATIN 2018: THEORETICAL INFORMATICS, 2018, 10807 : 873 - 885
  • [2] COUNTING PERFECT MATCHINGS AND THE SWITCH CHAIN
    Dyer, Martin
    Muller, Haiko
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1146 - 1174
  • [3] A New Direction for Counting Perfect Matchings
    Izumi, Taisuke
    Wadayama, Tadashi
    2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, : 591 - 598
  • [4] Counting perfect matchings in n-extendable graphs
    Doslic, Tomislav
    DISCRETE MATHEMATICS, 2008, 308 (11) : 2297 - 2300
  • [5] Counting Perfect Matchings in Chain Graphs with the Specific Colored Faces
    Saduakdee, Supaporn
    Maliwan, Pattana
    Singthong, Thitaporn
    Sirilap, Supatta
    Khemmani, Varanoot
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2024, 19 (03) : 677 - 686
  • [6] Perfect matchings and derangements on graphs
    Bucic, Matija
    Devlin, Pat
    Hendon, Mo
    Horne, Dru
    Lund, Ben
    JOURNAL OF GRAPH THEORY, 2021, 97 (02) : 340 - 354
  • [7] Counting the Number of Perfect Matchings in K5-free Graphs
    Straub, Simon
    Thierauf, Thomas
    Wagner, Fabian
    2014 IEEE 29TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2014, : 66 - 77
  • [8] Counting the Number of Perfect Matchings in K5-Free Graphs
    Simon Straub
    Thomas Thierauf
    Fabian Wagner
    Theory of Computing Systems, 2016, 59 : 416 - 439
  • [9] Counting the Number of Perfect Matchings in K 5-Free Graphs
    Straub, Simon
    Thierauf, Thomas
    Wagner, Fabian
    THEORY OF COMPUTING SYSTEMS, 2016, 59 (03) : 416 - 439
  • [10] HAFNIANS, PERFECT MATCHINGS AND GAUSSIAN MATRICES
    Rudelson, Mark
    Samorodnitsky, Alex
    Zeitouni, Ofer
    ANNALS OF PROBABILITY, 2016, 44 (04) : 2858 - 2888
12345