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