Finding bipartite subgraphs efficiently

DOI10.1016/J.IPL.2009.11.015MaRDI QIDQ991744zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi, Gy. Turán

Publication date 7 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.2527

zbMATH Keywords

algorithmsbipartite graphextremal graph theorygraph algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35)

Abstract: Polynomial algorithms are given for the following two problems: given a graph with $n$ vertices and $m$ edges, where $mge3n^{3/2}$, find a complete balanced bipartite subgraph with parts about $lnn/(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/lnn)$ vertices. Previous proofs of the existence of such objects, due to KH{o}v'ari-S'os-Tur'an, Chung-ErdH{o}s-Spencer, Bublitz and Tuza were non-constructive.

Recommendations

• Bipartite subgraphs
• Linear-Time Approximation Algorithms for the Max Cut Problem
• On the number of maximal bipartite subgraphs of a graph
• scientific article; zbMATH DE number 1339492
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three

Cites work

• scientific article; zbMATH DE number 3841905 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3752234 (Why is no real title available?)
• scientific article; zbMATH DE number 3613058 (Why is no real title available?)
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Decomposition of graphs and monotone formula size of homogeneous functions
• Disproving the Single Level Conjecture
• On a problem of K. Zarankiewicz
• On the Addressing Problem for Loop Switching
• The Algorithmic Aspects of the Regularity Lemma

Cited in

(9)

• Maximum bipartite subgraphs of Kneser graphs
• An efficient algorithm for enumerating chordal bipartite induced subgraphs in sparse graphs
• scientific article; zbMATH DE number 4070665 (Why is no real title available?)
• Finding even subgraphs even faster
• scientific article; zbMATH DE number 1796979 (Why is no real title available?)
• scientific article; zbMATH DE number 7765385 (Why is no real title available?)
• Succinct posets
• On the number of maximal bipartite subgraphs of a graph
• scientific article; zbMATH DE number 4047757 (Why is no real title available?)

This page was built for publication: Finding bipartite subgraphs efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991744)