Average case analysis of fully dynamic reachability for directed graphs
Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spaccamela (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying similar documents to “The random linear bottleneck assignment problem”
Average case analysis of fully dynamic reachability for directed graphs
Performance considerations on a random graph model for parallel processing
F. Afrati, A. Stafylopatis (1993)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Bootstrap percolation and diffusion in random graphs with given vertex degrees.
Amini, Hamed (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
An easy proof of the limit in the random assignment problem.
Wästlund, Johan (2009)
Electronic Communications in Probability [electronic only]
Similarity:
Sharp threshold functions for random intersection graphs via a coupling method.
Rybarczyk, Katarzyna (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Coloring the edges of a random graph without a monochromatic giant component.
Spöhel, Reto, Steger, Angelika, Thomas, Henning (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Encores on cores.
Cain, Julie, Wormald, Nicholas (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Entrywise bounds for eigenvectors of random graphs.
Mitra, Pradipta (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
Jean-Luc Lutton, Ernesto Bonomi (1986)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Constrainted graph processes.
Bolobás, Béla, Riordan, Oliver (2000)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms
Kunal Dutta, C.R. Subramanian (2014)
Discussiones Mathematicae Graph Theory
Similarity:
Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance...