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

Параметризованные алгоритмы графического представления графов (посмотреть исходный код)

1233 байта убрано , 30 марта 2016

м

4652

правки

@@ Строка 116: / Строка 116: @@
-Требуется: двудольный граф G = (V1, V2, E), целое число k, отношение линейного порядка<1 на V1, отношение частичного порядка <2 на V2. Результат: ДА в том и только том случае, если данный экземпляр задачи односторонней минимизации пересечений (OSCM) имеет решение
+[[Файл:PADG_code.png]]
-repeat
-Исчерпывающим образом применить правила редукции, соответственно корректируя <2 и k. Определить вершины, порядок которых был установлен при помощи транзитивности, и соответствующим образом скорректировать <2 и k, до тех пор, пока не останется вариантов изменения <2 и k: if k < 0 or <2 содержит и (x, y), и (y; x) then
-return НЕТ.
-else if 9fx; у} С V2 : не имеет места ни x <2 y, y <2 x then if OSCM-ST-simple(G,fc- 1;<1;<2 [ f(x, y)g) then
-return ДА 10:      else
-return OSCM-ST-simple(G ;k - 1; <b <2 [ f(y;x)g) end if else
-return ДА 15: end if