1964724
Optimal construction of edge-disjoint paths in random regular graphs
Given a graph G = (V, E) and a set of κ pairs of vertices in V, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of κ paths so found is edge-disjoint. (For arbitrary graphs the problem is NP-complete, although it is in P if κ is fixed.)We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph Gn,r, for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every Gn,r is such that all sets of κ = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum.
21211
Random Minimum Length Spanning Trees in Regular Graphs
r-regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that .
9860639
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
It is well known 9] that nding a maximal independent set in a graph is in class N C, and 10] that nding a maximal independent set in a hypergraph with xed dimension is in RN C. It is not known whether this latter problem remains in N C when the dimension is part of the input. We will study the problem when the problem instances are randomly chosen. It was shown in 6] that the expected running time of a simple parallel algorithm for nding the lexicographically rst maximal independent set (lfmis) in a random simple graph is logarithmic in the input size. In this paper, we will prove a generalization of this result. We show that if a random k-uniform hypergraph has vertex set f1; 2; : : : ; ng and its edges are chosen independently with probability p from the set of ? n k possible edges, then our algorithm nds the lfmis
448902
A general model of web graphs
We describe a very general model of a random graph process whose proportional degree sequence obeys a power law. Such laws have recently been observed in graphs associated with the world wide web.
2168830
Generating and Counting Hamilton Cycles in Random Regular Graphs
LetGbe chosen uniformly at random from the set G(r,n) ofr-regular graphs with vertex set n. We describe polynomial time algorithms thatwhp(i) find a Hamilton cycle inG, and (ii) approximately count the number of Hamilton cycles inG.
6616465
Multi-Coloured Hamilton Cycles In Random Edge-Coloured Graphs
We define a space of random edge-coloured graphs Gn,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 ≤ 21 such that, provided m ≥ K0n log n and κ ≥ K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 as the number of vertices n tends to infinity.
12252849
On the connectivity of randomm-orientable graphs and digraphs
We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex.We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences.We also examine the relationship between our results and certain results of Erdős and Rényi.