# Complexity of pmetis and kmetis algorithms

Hi,

What is the complexity of kmetis and pmetis algorithms used for graph partitioning ?

Thanks,

Anjali

Submitted by anjali on Sun, 2007-08-12 23:07

»

- Login to post comments

## RE: The complexity of kmetis is

The complexity of kmetis is approximately O(n + m + klog(k)) where n is the number of nodes, m the number of edges, and k the number of partitions.

The complexity of pmetis is O((n+m)*log(k)).