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)

Abstract

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 Creators ORCiD Kalyanasundaram, Subrahmanyam UNSPECIFIED
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
URI:	http://raiithold.iith.ac.in/id/eprint/2402
Publisher URL:	https://doi.org/10.1017/S0963548314000200
OA policy:	http://www.sherpa.ac.uk/romeo/issn/0963-5483/
Related URLs:	Google Scholar

Actions (login required)

View Item

Statistics for this ePrint Item