Гимади Э.Х. Чесноков Д.С. Шин Е.Ю.
Об одном классе задач кластеризации на сетевых моделях
Докладчик: Шин Е.Ю.
В работе рассматривается одна из задач кластеризации, возникающая
при создании поисковых систем. Доказана NP-трудность задачи в общем
случае, определен сложностной статус на некоторых типовых структурах
ориентированных графов таких как: полный ациклический орграф,
путевой граф, древовидные графы (OutTree и InTree). В
случае путевого графа и инвертированного дерева предложены точные
алгоритмы решения квадратичной временной сложности.
К списку докладов