scientific article; zbMATH DE number 1139976
From MaRDI portal
Publication:4385084
zbMATH Open0998.05058MaRDI QIDQ4385084FDOQ4385084
Authors: Jonathan Aronson, Alan Frieze, Boris Pittel 
Publication date: 11 November 2002
Title of this publication is not available (Why is that?)
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (44)
- Finding maximum matchings in random regular graphs in linear expected time
- A scaling limit for the length of the longest cycle in a sparse random digraph
- Random graphs with a fixed maximum degree
- Matchings on infinite graphs
- Distributed algorithms for random graphs
- A probabilistic algorithm for vertex cover
- Erratum to: ``Greedy matching: guarantees and limitations
- Understanding the correlation gap for matchings
- Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
- Karp-Sipser on random graphs with a fixed degree sequence
- Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
- On the number of circuits in random graphs
- Between 2- and 3-colorability
- Two faces of greedy leaf removal procedure on graphs
- Minors of a random binary matroid
- Finite size scaling for the core of large random hypergraphs
- A local algorithm and its percolation analysis of bipartite z-matching problem
- STACS 2004
- Normal convergence problem? Two moments and a recurrence may be the clues
- 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
- Invariant probability measures and dynamics of exponential linear type maps
- An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Counting connected graphs inside-out
- On the rank, kernel, and core of sparse random graphs
- A scaling limit for the length of the longest cycle in a sparse random graph
- Large deviations of the greedy independent set algorithm on sparse random graphs
- The mixing time of the giant component of a random graph
- Title not available (Why is that?)
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- Asymptotic enumeration of sparse graphs with a minimum degree constraint
- The average performance of the greedy matching algorithm
- Existence of absolutely continuous spectrum for Galton-Watson random trees
- The spread of fire on a random multigraph
- Power balance and apportionment algorithms for the United States Congress
- Greedy Local Search and Vertex Cover in Sparse Random Graphs
- Matching algorithms are fast in sparse random graphs
- The number of matchings in random graphs
- Greedy matching: guarantees and limitations
- The satisfiability threshold for \(k\)-XORSAT
- Edge percolation on a random regular graph of low degree
- Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
- On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4385084)
