Dynamic Hierarchical j-Tree Decomposition and Its Applications
Abstract
We develop a new algorithmic framework for designing approximation algorithms for cut-based optimization problems on capacitated undirected graphs that undergo edge insertions and deletions. Specifically, our framework dynamically maintains a variant of the hierarchical \(j\)-tree decomposition of [Madry FOCS’10], achieving a poly-logarithmic approximation factor to the graph’s cut structure and supporting edge updates in \(O(n^{\varepsilon})\) amortized update time, for any arbitrarily small constant \(\varepsilon \in (0,1)\).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 1128–1180
- Publication date
- 1 January 2026
- Language
- EN