86 citations · 344 across the 93 of their papers we have counts for
10 papers · 1 filter
Rainbow Hamilton cycles in random graphs
Alan Frieze, Po-Shen Loh
One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erdos-Renyi random graph G_{n,p} is around p ~ (log n + log lo…
Efficient algorithms for three-dimensional axial and planar random assignment problems
Alan Frieze, Gregory Sorkin
Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and ab…
Packing tight Hamilton cycles in 3-uniform hypergraphs
Alan Frieze, Michael Krivelevich, Po-Shen Loh
Let H be a 3-uniform hypergraph with N vertices. A tight Hamilton cycle C \subset H is a collection of N edges for which there is an ordering of the vertices v_1, ..., v_N such tha…
Loose Hamilton Cycles in Random Uniform Hypergraphs
Andrzej Dudek, Alan Frieze
In the random hypergraph each possible -tuple appears independently with probability . A loose Hamilton cycle is a cycle in which every pair of adjacent edges int…
Component structure of the vacant set induced by a random walk on a random graph
Colin Cooper, Alan Frieze
We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by th…
Average case performance of heuristics for multi-dimensional assignment problems
Alan Frieze, Gregory Sorkin
We consider multi-dimensional assignment problems in a probabilistic setting. Our main results are: (i) A new efficient algorithm for the 3-dimensional planar problem, based on enu…
Variations on Cops and Robbers
Alan Frieze, Michael Krivelevich, Po-Shen Loh
We consider several variants of the classical Cops and Robbers game. We treat the version where the robber can move R > 1 edges at a time, establishing a general upper bound of N /…
A note on the random greedy triangle-packing algorithm
Tom Bohman, Alan Frieze, Eyal Lubetzky
The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. We begin with a complete graph on vertices and proceed to remove the e…
Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Alan Frieze
In the random hypergraph H=H(n,p;3) each possible triple appears independently with probability p. A loose Hamilton cycle can be described as a sequence of edges {x_i,y_i,x_{i+1}\}…
Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs
Alan Frieze, Michael Krivelevich
We say that a -uniform hypergraph is a Hamilton cycle of type , for some , if there exists a cyclic ordering of the vertices of such that every ed…