|
|
| 1. |
Quasi‐random classes of hypergraphs |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 363-382
Fan R. K. Chung,
Preview
|
PDF (739KB)
|
|
摘要:
AbstractWe investigate the relations among a number of different graph properties fork‐uniformhypergraphs, which are shared by random hypergraphs. Various graph properties form equivalence classes which in turn constitute a natural hierarchy. The analogues for binary functions onk‐tuples and for hypergraphs with small density are also considered. Several classes are related to communication complexity and expander gra
ISSN:1042-9832
DOI:10.1002/rsa.3240010401
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
| 2. |
A random tree model associated with random graphs |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 383-402
David Aldous,
Preview
|
PDF (834KB)
|
|
摘要:
AbstractGrow a tree onnvertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum‐weight spanning tree question, when the edge‐weight distribution is allowed to vary almost arbitrarily wi
ISSN:1042-9832
DOI:10.1002/rsa.3240010402
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
| 3. |
Small cliques in random graphs |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 403-434
A. D. Barbour,
Svante Janson,
Michal Karoński,
Andrzej Ruciński,
Preview
|
PDF (1159KB)
|
|
摘要:
AbstractFord≥ 1,a d‐clique in a graphGis a completed‐vertex subgraph not contained in any larger complete subgraph ofG.We investigate the limit distribution of the number ofd‐cliques in the binomial random graphG(n, p),p=p
ISSN:1042-9832
DOI:10.1002/rsa.3240010403
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
| 4. |
On the chromatic number of random graphs |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 435-442
Colin McDiarmid,
Preview
|
PDF (275KB)
|
|
摘要:
AbstractWe consider random graphsGn,pwith fixed edge‐probabilityp.We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal ton/{2 logbn− 2 logblogbn+O(1)} whereb= 1/(1
ISSN:1042-9832
DOI:10.1002/rsa.3240010404
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
| 5. |
Linear arboricity of random regular graphs |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 443-445
Colin McDiarmid,
Bruce Reed,
Preview
|
PDF (137KB)
|
|
ISSN:1042-9832
DOI:10.1002/rsa.3240010405
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
| 6. |
Randomized broadcast in networks |
| |
Random Structures&Algorithms,
Volume 1,
Issue 4,
1990,
Page 447-460
Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal,
Preview
|
PDF (651KB)
|
|
摘要:
AbstractIn this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in the maintenance of replicated databases.
ISSN:1042-9832
DOI:10.1002/rsa.3240010406
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1990
数据来源: WILEY
|
|
首页
