  Given a bipartite graph, the maximum balanced biclique (\textsf{MBB})
problem, discovering a mutually connected while equal-sized disjoint sets with
the maximum cardinality, plays a significant role for mining the bipartite
graph and has numerous applications. Despite the NP-hardness of the
\textsf{MBB} problem, in this paper, we show that an exact \textsf{MBB} can be
discovered extremely fast in bipartite graphs for real applications. We propose
two exact algorithms dedicated for dense and sparse bipartite graphs
respectively. For dense bipartite graphs, an $\mathcal{O}^{*}( 1.3803^{n})$
algorithm is proposed. This algorithm in fact can find an \textsf{MBB} in near
polynomial time for dense bipartite graphs that are common for applications
such as VLSI design. This is because, using our proposed novel techniques, the
search can fast converge to sufficiently dense bipartite graphs which we prove
to be polynomially solvable. For large sparse bipartite graphs typical for
applications such as biological data analysis, an $\mathcal{O}^{*}(
1.3803^{\ddot{\delta}})$ algorithm is proposed, where $\ddot{\delta}$ is only a
few hundreds for large sparse bipartite graphs with millions of vertices. The
indispensible optimizations that lead to this time complexity are: we transform
a large sparse bipartite graph into a limited number of dense subgraphs with
size up to $\ddot{\delta}$ and then apply our proposed algorithm for dense
bipartite graphs on each of the subgraphs. To further speed up this algorithm,
tighter upper bounds, faster heuristics and effective reductions are proposed,
allowing an \textsf{MBB} to be discovered within a few seconds for bipartite
graphs with millions of vertices. Extensive experiments are conducted on
synthetic and real large bipartite graphs to demonstrate the efficiency and
effectiveness of our proposed algorithms and techniques.
