Параметризованные алгоритмы графического представления графов: различия между версиями

Перейти к навигации Перейти к поиску
Строка 116: Строка 116:




В различных публикациях рассматривались варианты этой задачи и родственные ей проблемы.
'''Варианты этой задачи и родственные ей проблемы''' широко рассматривались в литературе.


1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем исполнения O*(3k), которое впоследствии было улучшено до O*(2k)m[W].
1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем исполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>.


2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10].
2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10].
Источник — http://pco.iis.nsk.su/wega/index.php/Параметризованные_алгоритмы_графического_представления_графов