Applied Mathematics; Computational Theory and Mathematics; Control and Optimization; Discrete Mathematics and Combinatorics; Computer Science Applications
Disciplines :
Computer science
Author, co-author :
Hertz, Alain
Bonte, Sébastien ; Université de Mons - UMONS > Faculté des Sciences > Service des Systèmes d'information
Devillez, Gauvain ; Université de Mons - UMONS > Faculté des Sciences > Service Algorithmique
Mélot, Hadrien ; Université de Mons - UMONS > Faculté des Sciences > Service Algorithmique
E.O.D. Andriantiana V. Razanajatovo Misanantenaina S. Wagner The average size of matchings in graphs Graphs Comb 2020 36 3 539 560 4090510 10.1007/s00373-020-02136-1
N. Arnosti Greedy matching in bipartite random graphs Stochastic Syst 2021 12 133 4447004 10.1287/stsy.2021.0082
Aronson J, Dyer M, Frieze A, Suen S (1994) On the greedy heuristic for matchings. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (USA, 1994), SODA ’94, Society for Industrial and Applied Mathematics, pp. 141–149
J. Aronson M. Dyer A. Frieze S. Suen Randomized greedy matching. ii Random Struct. Algorithms 1995 6 1 55 73 1368835 10.1002/rsa.3240060107
B. Besser M. Poloczek Greedy matching: guarantees and limitations Algorithmica 2017 77 1 201 234 3594389 10.1007/s00453-015-0062-2
Devillez G, Hauweele P, Mélot H (2019) PHOEG Helps to Obtain Extremal Graphs. In: Operations Research Proceedings 2018 (GOR (Gesellschaft fuer Operations Research e.V.)) (sept. 12-14 2019), Fortz B, Labbé M, Eds., Springer, Cham, p. 251 (Paper 32)
R. Diestel Graph theory 2017 2 Berlin Springer-Verlag 10.1007/978-3-662-53622-3
T. Došlić T. Short Maximal matchings in polyspiro and benzenoid chains Appl Anal Discr Math 2021 15 1 179 200 4250092 10.2298/AADM161106003D
T. Došlić I. Zubac Counting maximal matchings in linear polymers Ars Math Contemp 2015 11 2 255 276 3570465 10.26493/1855-3974.851.167
M. Dyer A. Frieze Randomized greedy matching Random Struct Algorithms 1991 2 1 29 45 1099578 10.1002/rsa.3240020104
M. Dyer A. Frieze B. Pittel The average performance of the greedy matching algorithm Ann Appl Probab 1993 3 526 552 1221164 10.1214/aoap/1177005436
P. Flajolet R. Sedgewick Analytic combinatorics 2009 Cambridge Cambridge University Press 10.1017/CBO9780511801655
P.J. Flory Intramolecular reaction between neighboring substituents of vinyl polymers J Am Chem Soc 1939 61 6 1518 1521 10.1021/ja01875a053
A. Frieze A.J. Radcliffe S. Suen Analysis of a simple greedy matching algorithm on random cubic graphs Comb Probab Comput 1995 4 1 47 66 1336655 10.1017/S0963548300001474
Goel G, Tripathi P (2012) Matching with our eyes closed. In: 2012 IEEE 53rd annual symposium on foundations of computer science, IEEE, pp. 718–727
I. Gutman Distance of thorny graphs Publ l’Instit Math 1998 63 77 31 36 1633682
H. Hosoya Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons Bull Chem Soc Jpn 1971 44 2332 2339 10.1246/bcsj.44.2332
L. Lovász M.D. Plummer Matching theory 2009 Providence American Mathematical Soc
Magun J (1997) Greedy matching algorithms, an experimental study. In: Proceedings of the 1st workshop on algorithm engineering. 6:22–31
Z. Miller D. Pritikin On randomized greedy matchings Random Struct Algorithms 1997 10 3 353 383 1606234 10.1002/(SICI)1098-2418(199705)10:3<353::AID-RSA5>3.0.CO;2-V
Poloczek M, Szegedy M (2012) Randomized greedy algorithms for the maximum matching problem with new analysis. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, IEEE, pp. 708–717
T. Short Z. Ash The number of maximal matchings in polyphenylene chains Iran J Math Chem 2019 10 4 343 360
G. Tinhofer A probabilistic analysis of some greedy cardinality matching algorithms Ann Oper Res 1984 1 3 239 254 763561 10.1007/BF01874391
H. Van der Laan Le nombre plastique 1997 Leiden Brill Archive
M. Yannakakis F. Gavril Edge dominating sets in graphs SIAM J Appl Math 1980 38 3 364 372 579424 10.1137/0138030
