Finding bipartite subgraphs efficiently

Details Finding bipartite subgraphs efficiently Finding bipartite subgraphs efficiently

2009-05-15

arxiv.org/abs/0905.2527v1

Mathematics

Combinatorics

Scientific paper

Polynomial algorithms are given for the following two problems: given a graph with $n$ vertices and $m$ edges, where $m \ge 3 n^{3/2}$, find a complete balanced bipartite subgraph with parts about $\ln n/(\ln (n^2/m))$, given a graph with $n$ vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether $O(n^2 / \ln n)$ vertices. Previous proofs of the existence of such objects, due to K\H{o}v\'ari-S\'os-Tur\'an, Chung-Erd\H{o}s-Spencer, Bublitz and Tuza were non-constructive.

Affiliated with

Also associated with

No associations

Rating

Finding bipartite subgraphs efficiently 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 Finding bipartite subgraphs efficiently, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding bipartite subgraphs efficiently will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-524406