8 citations · 24 across the 23 of their papers we have counts for
4 papers · 1 filter
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
Gramoz Goranci, Monika Henzinger, Pan Peng
We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsifica…
Estimating Graph Parameters from Random Order Streams
Pan Peng, Christian Sohler
We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate…
Testable Bounded Degree Graph Properties Are Random Order Streamable
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degre…
Improved Guarantees for Vertex Sparsification in Planar Graphs
Gramoz Goranci, Monika Henzinger, Pan Peng
Graph Sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e…