On fully dynamic graph sparsifiers

DOI10.1109/FOCS.2016.44MaRDI QIDQ6946465zbMATH OpenFDO

Authors Ittai Abraham, David Durfee, Sebastian Krinninger, Ioannis Koutis, Richard Peng

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2016.44

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(7)

• Cut sparsification and succinct representation of submodular hypergraphs
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Dynamic inference in probabilistic graphical models
• A generalized matching reconfiguration problem
• Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
• k-leaf powers cannot be characterized by a finite set of forbidden induced subgraphs for k 5
• Fully dynamic algorithms for transitive reduction

This page was built for publication: On fully dynamic graph sparsifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946465)