Разреженное l_1 приближение. Полупотоковые алгоритмы на графах. Нижняя оценка для детерминированного алгоритма для s-t связности. Динамические задачи: инкрементальная, декрементальная, полная динамическая модель. Инкрементальные компоненты связности, двудольность, поиск минимального покрывающего дерева. Полная динамическая модель: компоненты связности, двудольность

Источники:

• Sparse Recovery Using Sparse Matrices, Anna Gilbert, Piotr Indyk, 2010
• Analyzing Graph Structure via Linear Measurements, Kook Jin Ahn, Sudipto Guha, Andrew McGregor, 2012
• https://en.wikipedia.org/wiki/Dynamic_problem_(algorithms)
• Динамические деревья: https://habrahabr.ru/company/spbau/blog/216733/