15th International Asian School-Seminar "Optimization Problems of complex systems", 26-30 August 2019.

Novosibirsk, Russia

• General information
• About school-seminar
• Program committee
• Organizing committee
• Topics
• Location
• Accommodation
• Important dates
• Abstract submission
• Registration fee
• Visa application
• Participants
• Reports
• Registration/Login

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.