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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bermolen, P., Jonckheere, M., Moyal, P.
Formato: JOUR
Materias:
Configuration model
Hydrodynamic limit
Measure-valued Markov process
Parking process
Random graph
Differential equations
Jamming
Markov processes
Degree distributions
Differential equation method
Exploration algorithms
Maximal independent set
Primary
Random graphs
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03044149_v127_n7_p2138_Bermolen
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03044149_v127_n7_p2138_Bermolen
record_format dspace
spelling todo:paper_03044149_v127_n7_p2138_Bermolen2023-10-03T15:20:39Z The jamming constant of uniform random graphs Bermolen, P. Jonckheere, M. Moyal, P. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Bermolen, P.
Jonckheere, M.
Moyal, P.
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.
format JOUR
author Bermolen, P.
Jonckheere, M.
Moyal, P.
author_facet Bermolen, P.
Jonckheere, M.
Moyal, P.
author_sort Bermolen, P.
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
url http://hdl.handle.net/20.500.12110/paper_03044149_v127_n7_p2138_Bermolen
work_keys_str_mv AT bermolenp thejammingconstantofuniformrandomgraphs
AT jonckheerem thejammingconstantofuniformrandomgraphs
AT moyalp thejammingconstantofuniformrandomgraphs
AT bermolenp jammingconstantofuniformrandomgraphs
AT jonckheerem jammingconstantofuniformrandomgraphs
AT moyalp jammingconstantofuniformrandomgraphs
_version_ 1807319719222444032

Ejemplares similares