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 条

[21] On perfect matchings in matching covered graphs
He, Jinghua
Wei, Erling
Ye, Dong
Zhai, Shaohui
JOURNAL OF GRAPH THEORY, 2019, 90 (04) : 535 - 546
[22] On the Perfect Matchings of Near Regular Graphs
Hou, Xinmin
GRAPHS AND COMBINATORICS, 2011, 27 (06) : 865 - 869
[23] On perfect matchings of complements of line graphs
Liu, Xiaoping
An, Xinhui
Wu, Baoyindureng
ARS COMBINATORIA, 2009, 90 : 45 - 54
[24] Perfect matchings in random intersection graphs
Mindaugas Bloznelis
Tomasz Łuczak
Acta Mathematica Hungarica, 2013, 138 : 15 - 33
[25] The Aα-spectral radius and perfect matchings of graphs
Zhao, Yanhua
Huang, Xueyi
Wang, Zhiwen
LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 631 : 143 - 155
[26] Perfect Matchings of Regular Bipartite Graphs
Lukot'ka, Robert
Rollova, Edita
JOURNAL OF GRAPH THEORY, 2017, 85 (02) : 525 - 532
[27] On the Perfect Matchings of Near Regular Graphs
Xinmin Hou
Graphs and Combinatorics, 2011, 27 : 865 - 869
[28] Perfect matchings in pruned grid graphs
Guichard, David R.
DISCRETE MATHEMATICS, 2008, 308 (24) : 6552 - 6557
[29] Perfect matchings in random intersection graphs
Bloznelis, M.
Luczak, T.
ACTA MATHEMATICA HUNGARICA, 2013, 138 (1-2) : 15 - 33
[30] On the number of perfect matchings of middle graphs
Lai, Jingchao
Yan, Weigen
Feng, Xing
DISCRETE APPLIED MATHEMATICS, 2025, 366 : 86 - 91

← 1 2 3 4 5 →