.
two algorithms are (quickly) described and compared here :
Performance of Two Algorithms In Minimum Sum of Diameters Clustering
Zubair Noman, Mynul Khan
Abstract : Minimum sum of diameters clustering can be solved by reduction to determination of the satisfiability of a 2- Conjunctive Normal Form or 2-SAT statement. Hansen provided an algorithm that solved O(nlogn) 2-SAT instances and ran with time complexity O(n^3logn) on a graph of size n. Sarnath provided an improved dynamic digraph algorithm that solved O(m) 2-SAT instances on a graph with m edges and ran with time complexity O(n^3). Algorithms were implemented to partition instances of a complete graph having n=50 to n=500 vertices where all the vertices are connected with each other. In tests of the two algorithms, the Sarnath algorithm consistently performed better to find the edges of largest length of two clusters such that the sum is minimized.
www.micsymposium.org/mics_2002/NOMAN.PDF
.
- Badges
- Science topic