Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/12140
Nаziv: | Semi-random graph process | Аutоri: | Ben-Eliezer O. Hefetz D. Kronenberg G. Parczyk O. Shikhelman C. Stojaković, Miloš |
Dаtum izdаvаnjа: | 1-јан-2019 | Čаsоpis: | Random Structures and Algorithms | Sažetak: | © Wiley Periodicals, Inc. We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties P, we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies P. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models. | URI: | https://open.uns.ac.rs/handle/123456789/12140 | ISSN: | 10429832 | DOI: | 10.1002/rsa.20887 |
Nаlаzi sе u kоlеkciјаmа: | PMF Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
6
prоvеrеnо 12.08.2023.
Prеglеd/i stаnicа
10
Prоtеklа nеdеljа
10
10
Prоtеkli mеsеc
0
0
prоvеrеnо 03.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.