Mostrar el registro sencillo del ítem
dc.contributor.author
Bermolen, Paola
dc.contributor.author
Jonckheere, Matthieu Thimothy Samson
dc.contributor.author
Moyal, Pascal
dc.date.available
2018-08-15T11:18:48Z
dc.date.issued
2017-07
dc.identifier.citation
Bermolen, Paola; Jonckheere, Matthieu Thimothy Samson; Moyal, Pascal; The jamming constant of uniform random graphs; Elsevier Science; Stochastic Processes And Their Applications; 127; 7; 7-2017; 2138-2178
dc.identifier.issn
0304-4149
dc.identifier.uri
http://hdl.handle.net/11336/55577
dc.description.abstract
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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Configuration Model
dc.subject
Hydrodynamic Limit
dc.subject
Measure-Valued Markov Process
dc.subject
Parking Process
dc.subject
Random Graph
dc.subject.classification
Matemática Pura
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
The jamming constant of uniform random graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2018-08-14T14:13:44Z
dc.journal.volume
127
dc.journal.number
7
dc.journal.pagination
2138-2178
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bermolen, Paola. Universidad de la República; Uruguay
dc.description.fil
Fil: Jonckheere, Matthieu Thimothy Samson. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina
dc.description.fil
Fil: Moyal, Pascal. Northwestern University; Estados Unidos. Universite de Technologie de Compiegne; Francia
dc.journal.title
Stochastic Processes And Their Applications
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.spa.2016.10.005
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0304414916301806
Archivos asociados