52 citations · 180 across the 41 of their papers we have counts for
9 papers · 1 filter
Typical values of extremal-weight combinatorial structures with independent symmetric weights
Yun Cheng, Yixue Liu, Tomasz Tkocz +1
Suppose that the edges of a complete graph are assigned weights independently at random and we ask for the weight of the minimal-weight spanning tree, or perfect matching, or Hamil…
Shortest paths with a cost constraint: a probabilistic analysis
Alan Frieze, Tomasz Tkocz
We consider a constrained version of the shortest path problem on the complete graphs whose edges have independent random lengths and costs. We establish the asymptotic value of th…
Minimum-weight combinatorial structures under random cost-constraints
Alan Frieze, Wesley Pegden, Gregory Sorkin +1
Recall that Janson showed that if the edges of the complete graph are assigned exponentially distributed independent random weights, then the expected length of a shortest pa…
A randomly weighted minimum arborescence with a random cost constraint
Alan Frieze, Tomasz Tkocz
We study the minimum spanning arborescence problem on the complete digraph where an edge has a weight and a cost , each of which is an independent unifor…
A randomly weighted minimum spanning tree with a random cost constraint
Alan Frieze, Tomasz Tkocz
We study the minimum spanning tree problem on the complete graph where an edge has a weight and a cost , each of which is an independent copy of the random var…
Random graphs with a fixed maximum degree
Alan Frieze, Tomasz Tkocz
We study the component structure of the random graph . Here and is sampled uniformly from , the set of graphs with vertex set ,…
On random multi-dimensional assignment problems
Alan Frieze, Wesley Pegden, Tomasz Tkocz
We study random multidimensional assignment problems where the costs decompose into the sum of independent random variables. In particular, in three dimensions, we assume that the…
On the cover time of the emerging giant
Alan Frieze, Wesley Pegden, Tomasz Tkocz
Let . It is known that if then w.h.p. has a unique giant largest component. We show that if in addition, $\varepsil…
A note on log-concave random graphs
Alan Frieze, Tomasz Tkocz
We establish a threshold for the connectivity of certain random graphs whose (dependent) edges are determined by the uniform distributions on generalized Orlicz balls, crucially us…