ALGORITHMIC THEORY OF RANDOM GRAPHS

Authors
FRIEZE A MCDIARMID C
Citation
A. Frieze et C. Mcdiarmid, ALGORITHMIC THEORY OF RANDOM GRAPHS, Random structures & algorithms, 10(1-2), 1997, pp. 5-42
Citations number
207
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
10
Issue
1-2
Year of publication
1997
Pages
5 - 42
Database
ISI
SICI code
1042-9832(1997)10:1-2<5:ATORG>2.0.ZU;2-M
Abstract
The theory of random graphs has been mainly concerned with structural properties, in particular the most likely values of various graph inva riants-see Bollobas [21]. There has been increasing interest in using random graphs as models for the average case analysis of graph algorit hms. In this paper we survey some of the results in this area. (C) 199 7 John Wiley & Sons, Inc.