Almost-smooth histograms and sliding-window graph algorithms

DOI10.1007/s00453-022-00988-yOpenAlexW2936994107MaRDI QIDQ2088588

David Reitblat, Robert Krauthgamer

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

matchinggraph algorithmssliding windowsymmetric normsstreamingSchatten p-normsubadditive problems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Simple planar graph partition into three forests
• Better streaming algorithms for the maximum coverage problem
• Data streams. Models and algorithms.
• On graph problems in a semi-streaming model
• Dynamic Graphs in the Sliding-Window Model
• Separation between Estimation and Approximation
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• A cost function property for plant location problems
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Planar Matching in Streams Revisited
• Maintaining Stream Statistics over Sliding Windows
• Streaming symmetric norms via measure concentration
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs