На спецкурсе было рассказано про задачу поиска минимальных разрезов и циклов в планарных графах. Был рассказан достаточно красивый вероятностный алгоритм поиска минимального разреза в планарном графе в невзвешенном случае, работающий за линейное время. Это достаточно новый результат, использующий технику Color Coding (Zwick, 1994).
Также был рассказан алгоритм для поиска минимального разреза для случая взвешенного графа. Этот алгоритм использует рассказанную ранее технику поиска циклических сепараторов в планарных графах. При этом итоговая сложность алгоритма поиска разреза получается 
На спецсеминаре проходил доклад Ильи Разенштейна, на котором рассказывалось про практические методы решения задачи коммивояжера (TSP). Известно, что данная задача является NP-трудной. Тем не менее задача очень важна для практических приложений, и поэтому её приходится решать. Есть два подхода к решению задачи — это поиск приближенного решения и переборные алгоритмы с отсечением. В докладе был подробно рассмотрен второй подход, Илья рассказал про алгоритм Branch&Bound и применением в нем различных эвристик. Важная часть алгоритма — это поиск хороших нижних и верхних оценок на решение задачи TSP с фиксированном префиксом.
cotass 