Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Friday, August 16 until 2:00 AM ET on Saturday, August 17 due to maintenance. We apologize for the inconvenience.

# Search for:All records

Creators/Authors contains: "Frieze, Alan"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

1. Abstract

Let be chosen independently and uniformly at random from the unit ‐dimensional cube . Let be given and let . The random geometric graph has vertex set and an edge whenever . We show that if each edge of is colored independently from one of colors and has the smallest value such that has minimum degree at least two, then contains a rainbow Hamilton cycle asymptotically almost surely.

more » « less
2. Abstract

We show that the threshold for having a rainbow copy of a power of a Hamilton cycle in a randomly edge colored copy of is within a constant factor of the uncolored threshold. Our proof requires times the minimum number of colors.

more » « less
3. Let $N=\binom{n}{2}$ and $s\geq 2$. Let $e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A MultiTree is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,\ldots,s$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $O(n\log n)$ bound for $s\geq 3$.
more » « less
4. We study the minimum spanning arborescence problem on the complete digraph [Formula: see text], where an edge e has a weight W e and a cost C e , each of which is an independent uniform random variable U s , where [Formula: see text] and U is uniform [Formula: see text]. There is also a constraint that the spanning arborescence T must satisfy [Formula: see text]. We establish, for a range of values for [Formula: see text], the asymptotic value of the optimum weight via the consideration of a dual problem.
more » « less