An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions

作者：Dellamonica Domingos Jr^*; Kalyanasundaram Subrahmanyam; Martin Daniel M; Roedl Vojtech; Shapira Asaf

来源：Combinatorics Probability & Computing, 2015, 24(2): 407-437.

DOI：10.1017/S0963548314000200

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 graph G in time O(|V(G)|(2)).

• 出版日期2015-3