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