An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Michael Martin, Vojtěch Rödl, A. Shapira · Combinatorics Probability Computing · 2014
In this paper we prove that two local conditions involving the degrees and co-degrees in a graph can be used to determine whether a given vertex partition is Frieze–Kannan regular. With a more refined version of these two local conditions we provide a deterministic algorithm that obtains a Frieze–Kannan regular partition of any graphGin timeO(|V(G)|2).