The jamming constant of uniform random graphs
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...
| Publicado: |
2017
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03044149_v127_n7_p2138_Bermolen http://hdl.handle.net/20.500.12110/paper_03044149_v127_n7_p2138_Bermolen |
| Aporte de: |
| id |
paper:paper_03044149_v127_n7_p2138_Bermolen |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_03044149_v127_n7_p2138_Bermolen2023-06-08T15:29:48Z The jamming constant of uniform random graphs Configuration model Hydrodynamic limit Measure-valued Markov process Parking process Random graph Differential equations Jamming Markov processes Configuration model Degree distributions Differential equation method Exploration algorithms Hydrodynamic limit Maximal independent set Primary Random graphs Graph theory 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. © 2016 Elsevier B.V. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03044149_v127_n7_p2138_Bermolen http://hdl.handle.net/20.500.12110/paper_03044149_v127_n7_p2138_Bermolen |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Configuration model Hydrodynamic limit Measure-valued Markov process Parking process Random graph Differential equations Jamming Markov processes Configuration model Degree distributions Differential equation method Exploration algorithms Hydrodynamic limit Maximal independent set Primary Random graphs Graph theory |
| spellingShingle |
Configuration model Hydrodynamic limit Measure-valued Markov process Parking process Random graph Differential equations Jamming Markov processes Configuration model Degree distributions Differential equation method Exploration algorithms Hydrodynamic limit Maximal independent set Primary Random graphs Graph theory The jamming constant of uniform random graphs |
| topic_facet |
Configuration model Hydrodynamic limit Measure-valued Markov process Parking process Random graph Differential equations Jamming Markov processes Configuration model Degree distributions Differential equation method Exploration algorithms Hydrodynamic limit Maximal independent set Primary Random graphs Graph theory |
| description |
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. © 2016 Elsevier B.V. |
| title |
The jamming constant of uniform random graphs |
| title_short |
The jamming constant of uniform random graphs |
| title_full |
The jamming constant of uniform random graphs |
| title_fullStr |
The jamming constant of uniform random graphs |
| title_full_unstemmed |
The jamming constant of uniform random graphs |
| title_sort |
jamming constant of uniform random graphs |
| publishDate |
2017 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03044149_v127_n7_p2138_Bermolen http://hdl.handle.net/20.500.12110/paper_03044149_v127_n7_p2138_Bermolen |
| _version_ |
1768545142316204032 |