Chicago Journal of Theoretical Computer Science

CJTCS Special Issue: CATS 2009

Selected papers from

2009 Computing: The Australasian Theory Symposium

held in Wellington, New Zealand January 20-23 2009.

Guest Editors: Rod Downey, Victoria University of Wellington, NZ

Prabhu Manyem, Shanghai University, PRC.

Article 2010-5

Published by the Department of Computer Science, The University of Chicago.

On the Structure of Classes of Random Graphs

András Faragó
Department of Computer Science
The University of Texas at Dallas

June 22, 2010

Many different random graph constructions are used to model large real life graphs, i.e., graphs that describe the structure of real systems. Often it is not clear, however, how the strength of the different models compare to each other, e.g., when does it hold that a certain model class contains another. We are particularly interested in random graph models that arise via abstract geometric constructions, motivated by the fact that these graphs can model wireless communication networks. We set up a general framework to compare the strength of random graph models, and present some results about the equality, inequality and proper containment of certain model classes, as well as some open problems.

DOI: 10.4086/cjtcs.2010.005

[] Special Issue, CATS 2009, Article 1 [] Article 3
[back] Special Issue [back] Published articles
[CJCTS home]