An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions. (March 2015)

• Record Type: Journal Article
• Authors: DELLAMONICA, DOMINGOS; KALYANASUNDARAM, SUBRAHMANYAM; MARTIN, DANIEL M.; RÖDL, VOJTĚCH; SHAPIRA, ASAF
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 2(2015:Mar.)
• Page Start: 407
• Page End: 437
• Publication Date: 2015-03
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000200
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>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 <italic>G</italic> in time <italic>O</italic>(|<italic>V</italic>(<italic>G</italic>)|²).</p> </abstract>