86 citations · 344 across the 93 of their papers we have counts for
9 papers · 1 filter
Cops and Robbers on Geometric Graphs
Andrew Beveridge, Andrzej Dudek, Alan Frieze +1
Cops and robbers is a turn-based pursuit game played on a graph . One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of th…
On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three
Alan Frieze
We describe and analyse a simple greedy algorithm \2G\ that finds a good 2-matching in the random graph $G=G_{n,cn}^{\d\geq 3}$ when . A 2-matching is a spanning subg…
On a sparse random graph with minimum degree {three}: Likely Posa's sets are large
Alan Frieze, Boris Pittel
We consider the likely size of the endpoint sets produced by Posa rotations, when applied to a longest path in a random graph with edges that is conditioned to hav…
Analyzing Walksat on random formulas
Amin Coja-Oghlan, Alan Frieze
Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds…
High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks
Alan Frieze, Charalampos E. Tsourakakis
In this work we analyze basic properties of Random Apollonian Networks \cite{zhang,zhou}, a popular stochastic model which generates planar graphs with power law properties. Specif…
Covering the edges of a random graph by cliques
Alan Frieze, Bruce Reed
The clique cover number of a graph G is the minimum number of cliques required to cover the edges of graph G. In this paper we consider the random graph G(n,p), for p constant. We…
Stationary distribution and cover time of random walks on random digraphs
Colin Cooper, Alan Frieze
We study properties of a simple random walk on the random digraph D_{n,p} when np={d\log n},\; d>1. We prove that whp the stationary probability pi_v of a vertex v is asymptotic to…
Packing tight Hamilton cycles in uniform hypergraphs
Deepak Bal, Alan Frieze
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…
Tight Hamilton Cycles in Random Uniform Hypergraphs
Andrzej Dudek, Alan Frieze
In this paper we show that is the sharp threshold for the existence of tight Hamilton cycles in random -uniform hypergraphs, for all . When we show that $1/n…