2024/10/23 by Mohamed Habib Aliou Diallo Aoudi, Pascal Moyal, Aoudi, Mohamed Habib Aliou Diallo +3
Computer Science · Physics and Astronomy · #05C80 #60J25 #91B68 #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Mathematics #Graph Theory and Algorithms #Probability (math.PR)
paper · doi:10.48550/arxiv.2410.18059
openalex publication_date 2024/10/23 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
In this work, we propose a large-graph limit estimate of the matching coverage for several matching algorithms, on general graphs generated by the configuration model. For a wide class of \em local matching algorithms, namely, algorithms that only use information on the immediate neighborhood of the explored nodes, we propose a joint construction of the graph by the configuration model, and of the resulting matching on the latter graph. This leads to a generalization in infinite dimension of the differential equation method of Wormald: We keep track of the matching algorithm over time by a measure-valued CTMC, for which we prove the convergence, to the large-graph limit, to a deterministic hydrodynamic limit, identified as the unique solution of a system of ODE's in the space of integer measures. Then, the asymptotic proportion of nodes covered by the matching appears as a simple function of that solution. We then make this solution explicit for three particular local algorithms: the classical \sc greedy algorithm, and then the \sc uni-min and \sc uni-max algorithms, two variants of the greedy algorithm that select, as neighbor of any explored node, its neighbor having the least (respectively largest) residual degree.