An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions

Dellamonica, D and Kalyanasundaram, Subrahmanyam and Martin, D M and Roedl, V and Shapira, A (2015) An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions. Combinatorics, Probability and Computing, 24 (2). pp. 407-437. ISSN 0963-5483

Full text not available from this repository. (Request a copy)


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)).

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Lemma; Approximation; Bounds; Graph
Subjects: Computer science > Computer programming, programs, data
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 24 May 2016 04:47
Last Modified: 20 Sep 2017 08:57
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2402 Statistics for this ePrint Item