The general problem of a multi-terminal cut is NP-hard. We can thus only resort to approximation algorithms and heuristics. Because of the size of our dataset, some of the approximation algorithms studied in the literature already have a prohibitive computational complexity even though they are polynomial, which makes the problem even harder.

The crucial question that arises is whether the problem definition itself could be relaxed so that it still gives useful clustering and effectively aides the user in dealing with large amounts of information. We attempted to redefine the problem and shown that limitiing the sizes of the clusters leads to a clear and readable visialization that enabled us to make some useful observations about the relationshuips between the different clusters of papers.

Ali Salehi 2005-04-29