Mostrar el registro sencillo del ítem

dc.contributor.author
Jonckheere, Matthieu Thimothy Samson  
dc.contributor.author
Sáenz, Manuel  
dc.date.available
2022-09-30T14:18:02Z  
dc.date.issued
2021-01  
dc.identifier.citation
Jonckheere, Matthieu Thimothy Samson; Sáenz, Manuel; Asymptotic optimality of degree-greedy discovering of independent sets in Configuration Model graphs; Elsevier Science; Stochastic Processes And Their Applications; 131; 1-2021; 122-150  
dc.identifier.issn
0304-4149  
dc.identifier.uri
http://hdl.handle.net/11336/171213  
dc.description.abstract
Finding independent sets of maximum size in fixed graphs is well known to be an NP-hard task. Using scaling limits, we characterise the asymptotics of sequential degree-greedy explorations and provide sufficient conditions for this algorithm to find an independent set of asymptotically optimal size in large sparse random graphs with given degree sequences. In the special case of sparse Erdös–Rényi graphs, our results allow to give a simple proof of the so-called e-phenomenon identified by Karp and Sipser for matchings and to give an alternative characterisation of the asymptotic independence number.  
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
HYDRODYNAMIC LIMITS  
dc.subject
MAXIMUM INDEPENDENT SETS  
dc.subject
RANDOM GRAPHS  
dc.subject
SEQUENTIAL ALGORITHMS  
dc.subject.classification
Estadística y Probabilidad  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Asymptotic optimality of degree-greedy discovering of independent sets in Configuration Model 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
2022-08-09T11:50:50Z  
dc.identifier.eissn
1879-209X  
dc.journal.volume
131  
dc.journal.pagination
122-150  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Jonckheere, Matthieu Thimothy Samson. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Calculo. - Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Calculo; Argentina  
dc.description.fil
Fil: Sáenz, Manuel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Calculo. - Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Calculo; Argentina  
dc.journal.title
Stochastic Processes And Their Applications  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0304414920303690?via%3Dihub  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.spa.2020.09.009  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1808.10358