Treffer: The average size of giant components between the double-jump
Title:
The average size of giant components between the double-jump
Authors:
Source:
Analysis of algorithmsAlgorithmica. 46(3-4):529-555
Publisher Information:
New York, NY: Springer, 2006.
Publication Year:
2006
Physical Description:
print, 31 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Graphe aléatoire, Random graph, Grafo aleatorio, Modélisation, Modeling, Modelización, Processus stochastique, Stochastic process, Proceso estocástico, Théorème limite, Limit theorem, Teorema límite, Double-jump, Giant components, Probabilistic/analytic combinatorics, Random graphs
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
LIPN -UMR 7030, Institut Galilée, Université de Paris-Nord, 99 Avenue J. B. Clément, 93430 Villetaneuse, France
ISSN:
0178-4617
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18442331
Database:
PASCAL Archive
Weitere Informationen
We study the sizes of connected components according to their excesses during a random graph process built with n vertices. The considered model is the continuous one defined in [17]. An ℓ-component is a connected component with ℓ edges more than vertices. ℓ is also called the excess of such a component. As our main result, we show that when ℓ and n/ℓ are both large, the expected number of vertices that ever belong to an ℓ-component is about 121/3ℓ1/3n2/3. We also obtain limit theorems for the number of creations of C-components.