An Algorithmic Version of the Blow-up Lemma

Details An Algorithmic Version of the Blow-up Lemma An Algorithmic Version of the Blow-up Lemma

1996-12-04

arxiv.org/abs/math/9612213v1

Mathematics

Combinatorics

Scientific paper

Recently we have 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, beside the Regularity Lemma, is the so-called Blow-up Lemma. This lemma helps to find bounded degree spanning subgraphs in $\varepsilon$-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 be found in time $O(nM(n))$, where $M(n)=O(n^{2.376})$ is the time needed to multiply two $n$ by $n$ matrices with 0,1 entries over the integers. We show that the algorithm can be parallelized and implemented in $NC^5$.

Affiliated with

Also associated with

No associations

Rating

An Algorithmic Version of the Blow-up Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algorithmic Version of the Blow-up Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Version of the Blow-up Lemma will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469553