Algorithmic theory of random graphs

作者：ALAN M. FRIEZE, Colin McDiarmid · 发表于：Random Structures and Algorithms · 年份：1997 · DOI：10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.3.co;2-6 · 被引用次数：39 · 研究领域：Advanced Graph Theory Research、Limits and Structures in Graph Theory、semigroups and automata theory

The theory of random graphs has been mainly concerned with structural properties, in particular the most likely values of various graph invariants—see Bollobàs [21]. There has been increasing interest in using random graphs as models for the average case analysis of graph algorithms. In this paper we survey some of the results in this area. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 5–42 (1997)