𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An algorithmic version of the blow-up lemma

✍ Scribed by János Komlós; Gabor N. Sarkozy; Endre Szemerédi

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
210 KB
Volume
12
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Recently we developed a new method in graph theory based on the regularity lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, besides the regularity lemma, is the so-called blow-up Ž w Ž .x lemma Komlos, Sarkozy, and Szemeredi Combinatorica, 17, 109᎐123 1997 . This lemma ´´¨h elps to find bounded degree spanning subgraphs in -regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the blow-up lemma. The desired subgraph, for an n-vertex graph, can Ž Ž .. Ž . Ž 2.376 . be found in time O nM n , where M n sO n is the time needed to multiply two n by n matrices with 0, 1 entires over the integers. We show that the algorithm can be parallelized and implemented in NC 5 .

📜 SIMILAR VOLUMES

cover
An Old Babylonian Version of the Gilgamesh Epic
✍ Anonymous 📂 Fiction 📅 2014 🏛 Sheba Blake Publishing 🌐 English ⚖ 74 KB

The Epic of Gilgamesh is roughly 4000 years old, making it one of the earliest known works of written literature. It comes from Mesopotamia (aka ancient Iraq), and features the Sumerian legends of the mythological hero-king Gilgamesh, who was actually thought to be a real ruler in the 27th century B

cover
Trimalchio: an early version of The great Gatsby
✍ Fitzgerald, Francis Scott 📂 Fiction 📅 2014 🏛 Scribner 🌐 en-US ⚖ 163 KB

For the legions of _Great Gatsby_ fans and scholars, F. Scott Fitzgerald's early version of his masterpiece provides a new understanding of Fitzgerald's working methods, fresh insight into his characters, and renewed appreciation of his genius--now available in ebook for the first time. Reading F.