Publication:4385084
From MaRDI portal
zbMath0998.05058MaRDI QIDQ4385084
Jonathan Aronson, Alan M. Frieze, Boris G. Pittel
Publication date: 11 November 2002
68W40: Analysis of algorithms
05C80: Random graphs (graph-theoretic aspects)
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Two faces of greedy leaf removal procedure on graphs, The spread of fire on a random multigraph, Random Graphs with a Fixed Maximum Degree, Minors of a random binary matroid, The number of matchings in random graphs, The Satisfiability Threshold fork-XORSAT, Between 2- and 3-colorability, Existence of absolutely continuous spectrum for Galton-Watson random trees, Finding maximum matchings in random regular graphs in linear expected time, Large deviations of the greedy independent set algorithm on sparse random graphs, A local algorithm and its percolation analysis of bipartite z-matching problem, A scaling limit for the length of the longest cycle in a sparse random digraph, Matchings on infinite graphs, Analysis of an iterated local search algorithm for vertex cover in sparse random graphs, Greedy matching: guarantees and limitations, Birth of a giant \((k_{1},k_{2})\)-core in the random digraph, Distributed algorithms for random graphs, Edge percolation on a random regular graph of low degree, Finite size scaling for the core of large random hypergraphs, Normal convergence problem? Two moments and a recurrence may be the clues, Counting connected graphs inside-out, Asymptotic enumeration of sparse graphs with a minimum degree constraint, A scaling limit for the length of the longest cycle in a sparse random graph, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs, Counting strongly-connected, moderately sparse directed graphs, On the number of circuits in random graphs, The mixing time of the giant component of a random graph, On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three, Karp–Sipser on Random Graphs with a Fixed Degree Sequence, Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables, An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
