| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427945 | Information Processing Letters | 2010 | 4 Pages |
Abstract
Polynomial algorithms are given for the following two problems:•given a graph with n vertices and m edges, find a complete balanced bipartite subgraph Kq,q with ,•given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n2/lnn) vertices.The first algorithm can be modified to have running time linear in m and find a Kq′,q′ with q′=⌊q/5⌋. Previous proofs of the existence of such objects, due to Kővári, Sós and Turán (1954) [10], , Chung, Erdős and Spencer (1983) [5], , Bublitz (1986) [4], and Tuza (1984) [13] were non-constructive.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
