The longest path in a random graph
From MaRDI portal
Publication:1166543
DOI10.1007/BF02579172zbMath0489.05052OpenAlexW2001735302MaRDI QIDQ1166543
János Komlós, Miklós Ajtai, Endre Szemerédi
Publication date: 1981
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579172
Special processes (60K99) Paths and cycles (05C38) Combinatorial probability (60C05) Graph theory (05C99)
Related Items
Finding Hamilton cycles in sparse random graphs, Induced trees in sparse random graphs, On tree census and the giant component in sparse random graphs, On large matchings and cycles in sparse random graphs, Crux and Long Cycles in Graphs, Cycles in a random graph near the critical point, Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths, Grids in random graphs, Trees in sparse random graphs, Long paths in sparse random graphs, Smoothed Analysis on Connected Graphs, A note on long cycles in sparse random graphs, Finding paths in sparse random graphs requires many queries, Perfect matchings in random subgraphs of regular bipartite graphs, Longest and shortest cycles in random planar graphs, Rainbow trees in uniformly edge‐colored graphs, Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs, Cycle Factors and Renewal Theory, Heavy and light paths and Hamilton cycles, Long paths in heterogeneous random subgraphs of graphs with large minimum degree, Turán‐type problems for long cycles in random and pseudo‐random graphs, The phase transition in site percolation on pseudo-random graphs, Scaling window for mean-field percolation of averages, Largest random component of a k-cube, Exponential extinction time of the contact process on rank-one inhomogeneous random graphs, An analogue of the Erdős-Gallai theorem for random graphs, Client-waiter games on complete and random graphs, Embedding nearly-spanning bounded degree trees, Expanders Are Universal for the Class of All Spanning Trees, On depth first search trees in \(m\)-out digraphs, Paths and cycles in random subgraphs of graphs with large minimum degree, Longest Paths in Random Hypergraphs, Parallel processing of graph reachability in databases, A scaling limit for the length of the longest cycle in a sparse random graph, Last passage percolation on the complete graph, The giant component threshold for random regular graphs with edge faults H. Prodinger, Ramsey games with giants, Acquaintance Time of Random Graphs Near Connectivity Threshold, The chromatic number of random graphs at the double-jump threshold, Random Graphs In A Neural Computation Model, Large cycles in random generalized Johnson graphs, Long paths and cycles in random subgraphs of graphs with large minimum degree, The order of the largest complete minor in a random graph, On the subgraph query problem, Barak-Erdős graphs and the infinite-bin model, Longest cycles in sparse random digraphs, A Random Graph With a Subcritical Number of Edges, Rainbow Hamilton Cycles in Randomly Colored Randomly Perturbed Dense Graphs, The phase transition in random graphs: A simple proof, Loose cores and cycles in random hypergraphs, How many random edges make a graph Hamiltonian?, Unnamed Item, Component structure in the evolution of random hypergraphs, Expansion in supercritical random subgraphs of the hypercube and its consequences, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition, Random 2-SAT and unsatisfiability, Sharp threshold for the appearance of certain spanning trees in random graphs, Randomness in interactive proofs
Cites Work
