Abstract
Approximating graphs by j-trees is a powerful algorithmic paradigm that has proven effective in significantly speeding up cut-based optimization problems, approximate maximum flows, and exact minimum cost-flow computations.
In this talk, I will explain how to dynamically maintain j-trees and discuss some of the implications of this result.
Joint work with Li Chen, Monika Henzinger, Richard Peng and Thatchaphol Saranurak.