Кластеризация на основе эффективности: различия между версиями

Раджамаран и Вонг [ ] предложили оптимальный алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы с применением обобщенной модели задержки.

Теорема 1. Существует алгоритм, вычисляющий оптимальную кластеризацию для задачи кластеризации схемы за время O(n2 log n + nm), где n и m – количество вершин и ребер заданной комбинационной сети, соответственно.

Теорема 2. Для задачи кластеризации схемы может быть найдено оптимальное решение с учетом любых монотонных ограничений кластеризации за время, полиномиальное относительно размера схемы.