✦ LIBER ✦

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Scribed by Boris Pittel; Robert S. Weishaar

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 164 KB
Volume: 23
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0827

No coin nor oath required. For personal study only.

✦ Synopsis

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random graph and on at most three consecutive integers for a random tree.

📜 SIMILAR VOLUMES

On the complexity of branch-and-bound se

On the complexity of branch-and-bound search for random trees

✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

On the profile of random trees

✍ Michael Drmota; Bernhard Gittenberger 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB 👁 2 views

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe

On the Mean and Variance of Cover Times

On the Mean and Variance of Cover Times for Random Walks on Graphs

✍ Frank Ball; Bruce Dunham; A Hirschowitz 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 141 KB

A method is described for calculating the mean cover time for a particle performing a simple random walk on the vertices of a finite connected graph. The method also yields the variance and generating function of the cover time. A computer program is available which utilises the approach to provide

On-line multiscale filtering of random a

On-line multiscale filtering of random and gross errors without process models

✍ Mohamed N. Nounou; Bhavik R. Bakshi 📂 Article 📅 1999 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 246 KB 👁 2 views

Upper bounds on the height difference of

Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into ℤ

✍ Itai Benjamini; Gideon Schechtman 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for