Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Journal article
Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
Journal of applied probability, v 59(2), pp 299-324
Jun 2022
Abstract
We study two models of an age-biased graph process: the
$\delta$
-version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with m attachments for each of the incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for
$m=1$
, to a limit whose distribution is a mixture of two beta distributions and a single beta distribution respectively, and that for
$m>1$
the limit is 1. We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine – for each model and each greedy algorithm – both a limiting fraction of vertices involved and an almost sure convergence rate.
Metrics
3 Record Views
Details
- Title
- Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
- Creators
- Hüseyin Acan - Drexel UniversityAlan Frieze - Carnegie Mellon UniversityBoris Pittel - Ohio State University
- Publication Details
- Journal of applied probability, v 59(2), pp 299-324
- Publisher
- Cambridge University Press
- Number of pages
- 26
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000792250100001
- Scopus ID
- 2-s2.0-85129640076
- Other Identifier
- 991019168821204721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Statistics & Probability