Result: A Sequential Algorithm for Generating Random Graphs : APPROX+RANDOM

Title:
A Sequential Algorithm for Generating Random Graphs : APPROX+RANDOM
Authors:
BAYATI, Mohsen, JEONG HAN KIM, SABERI, Amin
Source:
Algorithmica. 58(4):860-910
Publisher Information:
Heidelberg: Springer, 2010.
Publication Year:
2010
Physical Description:
print, 40 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, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Approximation asymptotique, Asymptotic approximation, Aproximación asintótica, Arête graphe, Edge(graph), Arista gráfico, Comptage, Counting, Contaje, Degré graphe, Graph degree, Grado grafo, Echantillonnage importance, Importance sampling, Graphe aléatoire, Random graph, Grafo aleatorio, Graphe régulier, Regular graph, Grafo regular, Méthode séquentielle, Sequential method, Método secuencial, Temps linéaire, Linear time, Tiempo lineal, Temps polynomial, Polynomial time, Tiempo polinomial, FPRAS, Random graphs, Sequential importance sampling
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
Department of Electrical Engineering, Stanford University, Stanford, CA 94305-9510, United States
Department of Mathematics, Yonsei University, Yonsei, Korea, Republic of
Departments of Management Science and Engineering, Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305, United States
ISSN:
0178-4617
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=23384053
Rights:
Copyright 2015 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.23384053
Database:
PASCAL Archive

Further Information

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d¡)ni=1 with maximum degree dmax = O(m1/4―τ), our algorithm generates almost uniform random graphs with that degree sequence in time O(mdmax) where m = 1/2 Σi di is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52―67, 1990) has a running time of O(m2d2max). Our method also gives an independent proof of McKay's estimate (McKay in Ars Combinatoria A 19:15―25, 1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of dmax = O(m1/4―τ). Moreover, we show that for d = O(n1/2―τ), our algorithm can generate an asymptotically uniform d-regular graph. Our results improve the previous bound of d = O(n1/3―τ) due to Kim and Vu (Adv. Math. 188:444―469, 2004) for regular graphs.