Finding bipartite subgraphs efficiently

Simple item page
dc.creatorMubayi, D.
dc.creatorTuran, G.
dc.date2009-05-15
dc.date.accessioned2026-07-07T13:15:37Z
dc.date.available2026-07-07T13:15:37Z
dc.descriptionPolynomial 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ővári-Sós-Turán, Chung-Erdős-Spencer, Bublitz and Tuza were non-constructive.
dc.identifierhttps://arxiv.org/abs/0905.2527
dc.identifierhttp://arxiv.org/abs/0905.2527
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230525
dc.subjectCombinatorics
dc.titleFinding bipartite subgraphs efficiently
dc.typetext

Files

Collections

arXiv