Título:
The jamming constant of uniform random graphs
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Bermolen, Paola
Jonckheere, Matthieu
Moyal, Pascal
Jonckheere, Matthieu
Moyal, Pascal
Tutor:
Tipo de documento:
Preprint
Editor:
Palabras clave:
Random graph;
Configuration model
Parking process
Measure-valued Markov process
Hydrodynamic limit
Configuration model
Parking process
Measure-valued Markov process
Hydrodynamic limit
Descriptores:
Telecomunicaciones
Año de publicación:
2017
Contenido:
Resumen:
By constructing jointly a random graph and an associated exploration process, we define the dynamics of a “parking process” on a class of uniform random graphs as a measure-valued Markov process, representing the empirical degree distribution of non-explored nodes. We then establish a functional law of large numbers for this process as the number of vertices grows to infinity, allowing us to assess the jamming constant of the considered random graphs, i.e. the size of the maximal independent set discovered by the exploration algorithm. This technique, which can be applied to any uniform random graph with a given–possibly unbounded–degree distribution, can be seen as a generalization in the space of measures, of the differential equation method introduced by Wormald
Descripción:
Artículo publicado en Stochastic Processes and their Applications, v.127, no. 7, 2017, pp. 2138-2178
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
Citación:
Bermolen, P, Jonckheere, M, Moyal, P. "The jamming constant of uniform random graphs" [Preprint] Publicado en: Stochastic Processes and their Applications, v.127, no. 7, 2017, pp. 2138-2178. https://doi.org/10.1016/j.spa.2016.10.005
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Telecomunicaciones
Grupo de investigación:
Análisis de Redes, Tráfico y Estadísticas de Servicios
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| BJM17.pdf | — | 405.7 KB | Adobe PDF |