3 citations · 11 across the 32 of their papers we have counts for
4 papers · 1 filter
Finding perfect matchings in random regular graphs in linear time
Michael Anastos
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but d…
Finding perfect matchings in random cubic graphs in linear time
Michael Anastos, Alan Frieze
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but d…
On the connectivity threshold for colorings of random graphs and hypergraphs
Michael Anastos, Alan Frieze
Let denote the set of proper -colorings of the hypergraph . Let be the graph with vertex set and an edge ${σ,τ\}$ where are colorings iff $h(…
How many randomly colored edges make a randomly colored dense graph rainbow hamiltonian or rainbow connected?
Michael Anastos, Alan Frieze
In this paper we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular we…