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 条
  • [31] Counting the maximal and perfect matchings in benzenoid chains
    Shi, Lingjuan
    Deng, Kai
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2023, 447
  • [32] An algorithm to solve the partition into perfect matchings problem in halin graphs
    Lu, Yunting
    Lou, Dingjun
    [J]. COMPUTATIONAL SCIENCE - ICCS 2007, PT 3, PROCEEDINGS, 2007, 4489 : 410 - +
  • [33] Fullerene graphs with exponentially many perfect matchings
    Doslic, Tomislav
    [J]. JOURNAL OF MATHEMATICAL CHEMISTRY, 2007, 41 (02) : 183 - 192
  • [34] Perfect Matchings in Edge-Transitive Graphs
    Marandi, A.
    Nejah, A. H.
    Behmaram, A.
    [J]. IRANIAN JOURNAL OF MATHEMATICAL CHEMISTRY, 2014, 5 : S27 - S33
  • [35] Graphs of non-crossing perfect matchings
    Hernando, C
    Furtado, F
    Noy, M
    [J]. GRAPHS AND COMBINATORICS, 2002, 18 (03) : 517 - 532
  • [36] Removal of subgraphs and perfect matchings in graphs on surfaces
    Aldred, R. E. L.
    Fujisawa, Jun
    [J]. JOURNAL OF GRAPH THEORY, 2023, 102 (02) : 304 - 321
  • [37] Perfect Matchings in Total Domination Critical Graphs
    Michael A. Henning
    Anders Yeo
    [J]. Graphs and Combinatorics, 2011, 27 : 685 - 701
  • [38] On the spectral radius of unicyclic graphs with perfect matchings
    Chang, A
    Tian, F
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 370 : 237 - 250
  • [39] Perfect matchings in random polyomino chain graphs
    Wei, Shouliu
    Ke, Xiaoling
    Lin, Fenggen
    [J]. JOURNAL OF MATHEMATICAL CHEMISTRY, 2016, 54 (03) : 690 - 697
  • [40] The Wiener index of bicyclic graphs with perfect matchings
    Tan, Shangwang
    [J]. JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES, 2019, 40 (04) : 931 - 956
12345