Near-optimal fully dynamic densest subgraph

DOI10.1145/3357713.3384327MaRDI QIDQ5144907zbMATH OpenOpenAlexFDO

Authors Saurabh Sawlani, Junxing Wang

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.03037

zbMATH Keywords

data structuresdense subgraph discoveryfully dynamic algorithmgraph orientationlinear programming dual

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(12)

• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Brief announcement
• Improved dynamic colouring of sparse graphs
• Distributed dense subgraph detection and low outdegree orientation
• Optirefine: densest subgraphs and maximum cuts with k refinements
• Fine-grained complexity lower bounds for families of dynamic graphs
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Local density and its distributed approximation
• Approximating densest subgraph in geometric intersection graphs
• From theory to practice: engineering approximation algorithms for dynamic orientation
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism
• On deleting vertices to reduce density in graphs and supermodular functions

This page was built for publication: Near-optimal fully dynamic densest subgraph

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