Gimadi E. Chesnokov D. Shin E.
One class of clusterization problems in network models
Reporter: Shin E.
One clustering problem, which arises in design of search systems, is considered.
$NP$-hardness of the general case of the problem is proved.
A complexity status is determined for the cases with certain particular structures of the directed graph, such as:
Complete Acyclic graph, Path graph, OutTree and InTree graphs.
For the cases of Path and InTree graphs the exact algorithms with quadratic complexity are proposed.NP-hardness of the general case of the problem is proved.
To reports list