{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:45:24Z","timestamp":1757313924159,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s10878-024-01144-8","type":"journal-article","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T18:01:58Z","timestamp":1712253718000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The average size of maximal matchings in graphs"],"prefix":"10.1007","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7253-3867","authenticated-orcid":false,"given":"Alain","family":"Hertz","sequence":"first","affiliation":[]},{"given":"S\u00e9bastien","family":"Bonte","sequence":"additional","affiliation":[]},{"given":"Gauvain","family":"Devillez","sequence":"additional","affiliation":[]},{"given":"Hadrien","family":"M\u00e9lot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,4]]},"reference":[{"issue":"3","key":"1144_CR1","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s00373-020-02136-1","volume":"36","author":"EOD Andriantiana","year":"2020","unstructured":"Andriantiana EOD, Razanajatovo Misanantenaina V, Wagner S (2020) The average size of matchings in graphs. Graphs Comb 36(3):539\u2013560","journal-title":"Graphs Comb"},{"key":"1144_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/stsy.2021.0082","volume":"12","author":"N Arnosti","year":"2021","unstructured":"Arnosti N (2021) Greedy matching in bipartite random graphs. Stochastic Syst 12:133","journal-title":"Stochastic Syst"},{"key":"1144_CR3","unstructured":"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 \u201994, Society for Industrial and Applied Mathematics, pp.\u00a0141\u2013149"},{"issue":"1","key":"1144_CR4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/rsa.3240060107","volume":"6","author":"J Aronson","year":"1995","unstructured":"Aronson J, Dyer M, Frieze A, Suen S (1995) Randomized greedy matching. ii. Random Struct. Algorithms 6(1):55\u201373","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"1144_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-015-0062-2","volume":"77","author":"B Besser","year":"2017","unstructured":"Besser B, Poloczek M (2017) Greedy matching: guarantees and limitations. Algorithmica 77(1):201\u2013234","journal-title":"Algorithmica"},{"key":"1144_CR6","doi-asserted-by":"crossref","unstructured":"Devillez G, Hauweele P, M\u00e9lot 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\u00e9 M, Eds., Springer, Cham, p.\u00a0251 (Paper 32)","DOI":"10.1007\/978-3-030-18500-8_32"},{"key":"1144_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph theory","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory, 2nd edn. Springer-Verlag, Berlin","edition":"2"},{"issue":"1","key":"1144_CR8","doi-asserted-by":"publisher","first-page":"179","DOI":"10.2298\/AADM161106003D","volume":"15","author":"T Do\u0161li\u0107","year":"2021","unstructured":"Do\u0161li\u0107 T, Short T (2021) Maximal matchings in polyspiro and benzenoid chains. Appl Anal Discr Math 15(1):179\u2013200","journal-title":"Appl Anal Discr Math"},{"issue":"2","key":"1144_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.26493\/1855-3974.851.167","volume":"11","author":"T Do\u0161li\u0107","year":"2015","unstructured":"Do\u0161li\u0107 T, Zubac I (2015) Counting maximal matchings in linear polymers. Ars Math Contemp 11(2):255\u2013276","journal-title":"Ars Math Contemp"},{"issue":"1","key":"1144_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/rsa.3240020104","volume":"2","author":"M Dyer","year":"1991","unstructured":"Dyer M, Frieze A (1991) Randomized greedy matching. Random Struct Algorithms 2(1):29\u201345","journal-title":"Random Struct Algorithms"},{"key":"1144_CR11","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1214\/aoap\/1177005436","volume":"3","author":"M Dyer","year":"1993","unstructured":"Dyer M, Frieze A, Pittel B (1993) The average performance of the greedy matching algorithm. Ann Appl Probab 3:526\u2013552","journal-title":"Ann Appl Probab"},{"key":"1144_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet P, Sedgewick R (2009) Analytic combinatorics. Cambridge University Press, Cambridge"},{"issue":"6","key":"1144_CR13","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1021\/ja01875a053","volume":"61","author":"PJ Flory","year":"1939","unstructured":"Flory PJ (1939) Intramolecular reaction between neighboring substituents of vinyl polymers. J Am Chem Soc 61(6):1518\u20131521","journal-title":"J Am Chem Soc"},{"issue":"1","key":"1144_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1017\/S0963548300001474","volume":"4","author":"A Frieze","year":"1995","unstructured":"Frieze A, Radcliffe AJ, Suen S (1995) Analysis of a simple greedy matching algorithm on random cubic graphs. Comb Probab Comput 4(1):47\u201366","journal-title":"Comb Probab Comput"},{"key":"1144_CR15","doi-asserted-by":"crossref","unstructured":"Goel G, Tripathi P (2012) Matching with our eyes closed. In: 2012 IEEE 53rd annual symposium on foundations of computer science, IEEE, pp.\u00a0718\u2013727","DOI":"10.1109\/FOCS.2012.19"},{"issue":"77","key":"1144_CR16","first-page":"31","volume":"63","author":"I Gutman","year":"1998","unstructured":"Gutman I (1998) Distance of thorny graphs. Publ l\u2019Instit Math 63(77):31\u201336","journal-title":"Publ l\u2019Instit Math"},{"key":"1144_CR17","doi-asserted-by":"publisher","first-page":"2332","DOI":"10.1246\/bcsj.44.2332","volume":"44","author":"H Hosoya","year":"1971","unstructured":"Hosoya H (1971) Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull Chem Soc Jpn 44:2332\u20132339","journal-title":"Bull Chem Soc Jpn"},{"issue":"4","key":"1144_CR18","first-page":"8","volume":"24","author":"S Huntemann","year":"2021","unstructured":"Huntemann S, McKay NA (2021) Counting domineering positions. J Integer Seq 24(4):8","journal-title":"J Integer Seq"},{"issue":"6","key":"1144_CR19","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1063\/1.1744351","volume":"28","author":"JL Jackson","year":"1958","unstructured":"Jackson JL, Montroll EW (1958) Free radical statistics. J Chem Phys 28(6):1101\u20131109","journal-title":"J Chem Phys"},{"key":"1144_CR20","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz L, Plummer MD (2009) Matching theory, vol 367. American Mathematical Soc, Providence"},{"key":"1144_CR21","doi-asserted-by":"crossref","unstructured":"Magun J (1997) Greedy matching algorithms, an experimental study. In: Proceedings of the 1st workshop on algorithm engineering. 6:22\u201331","DOI":"10.1145\/297096.297131"},{"issue":"3","key":"1144_CR22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<353::AID-RSA5>3.0.CO;2-V","volume":"10","author":"Z Miller","year":"1997","unstructured":"Miller Z, Pritikin D (1997) On randomized greedy matchings. Random Struct Algorithms 10(3):353\u2013383","journal-title":"Random Struct Algorithms"},{"key":"1144_CR23","doi-asserted-by":"crossref","unstructured":"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.\u00a0708\u2013717","DOI":"10.1109\/FOCS.2012.20"},{"issue":"4","key":"1144_CR24","first-page":"343","volume":"10","author":"T Short","year":"2019","unstructured":"Short T, Ash Z (2019) The number of maximal matchings in polyphenylene chains. Iran J Math Chem 10(4):343\u2013360","journal-title":"Iran J Math Chem"},{"issue":"3","key":"1144_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01874391","volume":"1","author":"G Tinhofer","year":"1984","unstructured":"Tinhofer G (1984) A probabilistic analysis of some greedy cardinality matching algorithms. Ann Oper Res 1(3):239\u2013254","journal-title":"Ann Oper Res"},{"key":"1144_CR26","volume-title":"Le nombre plastique","author":"H Van der Laan","year":"1997","unstructured":"Van der Laan H (1997) Le nombre plastique. Brill Archive, Leiden"},{"issue":"3","key":"1144_CR27","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis M, Gavril F (1980) Edge dominating sets in graphs. SIAM J Appl Math 38(3):364\u2013372","journal-title":"SIAM J Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01144-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01144-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01144-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T19:06:18Z","timestamp":1713985578000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01144-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["1144"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01144-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,4]]},"assertion":[{"value":"12 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"46"}}