Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/12140
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ben-Eliezer O. | en_US |
dc.contributor.author | Hefetz D. | en_US |
dc.contributor.author | Kronenberg G. | en_US |
dc.contributor.author | Parczyk O. | en_US |
dc.contributor.author | Shikhelman C. | en_US |
dc.contributor.author | Stojaković, Miloš | en_US |
dc.date.accessioned | 2020-03-03T14:47:19Z | - |
dc.date.available | 2020-03-03T14:47:19Z | - |
dc.date.issued | 2019-01-01 | - |
dc.identifier.issn | 10429832 | en_US |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/12140 | - |
dc.description.abstract | © 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. | en |
dc.relation.ispartof | Random Structures and Algorithms | en |
dc.title | Semi-random graph process | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.doi | 10.1002/rsa.20887 | - |
dc.identifier.scopus | 2-s2.0-85074361374 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/85074361374 | - |
dc.description.version | Unknown | en_US |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.orcid | 0000-0002-2545-8849 | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
SCOPUSTM
Citations
6
checked on Aug 12, 2023
Page view(s)
10
Last Week
10
10
Last month
0
0
checked on May 3, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.