✦ LIBER ✦

Maximum Weight Partial Colorings on Sparse Random Graphs

✍ Scribed by Jaslar, Steven; Tatikonda, Sekhar

Book ID: 118197075
Publisher: Society for Industrial and Applied Mathematics
Year: 2011
Tongue: English
Weight: 257 KB
Volume: 25
Category: Article
ISSN: 0895-4801
DOI: 10.1137/090755771

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

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 gr

Maximum matchings in sparse random graph

Maximum matchings in sparse random graphs: Karp–Sipser revisited

✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB 👁 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3

Finding a Maximum Independent Set in a S

Finding a Maximum Independent Set in a Sparse Random Graph

✍ Feige, Uriel; Ofek, Eran 📂 Article 📅 2008 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 333 KB

Random coloring evolution on graphs

✍ Xin Xing Chen; Jian Gang Ying 📂 Article 📅 2010 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 178 KB

On -Diagonal Colorings of Embedded Graph

On -Diagonal Colorings of Embedded Graphs of Low Maximum Face Size

✍ Hunter S. Snevily; James A. Foster 📂 Article 📅 1998 🏛 Springer Japan 🌐 English ⚖ 145 KB

On large matchings and cycles in sparse

On large matchings and cycles in sparse random graphs

✍ A.M Frieze 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce