An Optimal Algorithm for Checking Regularity

We present a deterministic algorithm ${\cal A}$ that, in O(m2 ) time, verifies whether a given m by m bipartite graph G is regular, in the sense of Szemerédi [Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes (Orsay, 1976), Colloques Internationaux CNRS 260, CNRS, Paris... View More