
Fully Dynamic FourVertex Subgraph Counting
This paper presents a comprehensive study of algorithms for maintaining ...
read it

Differentially Private Algorithms for Graphs Under Continual Observation
Differentially private algorithms protect individuals in data analysis s...
read it

On the Complexity of WeightDynamic Network Algorithms
While operating communication networks adaptively may improve utilizatio...
read it

Symbolic Time and Space Tradeoffs for Probabilistic Verification
We present a faster symbolic algorithm for the following central problem...
read it

Recent Advances in Fully Dynamic Graph Algorithms
In recent years, significant advances have been made in the design and a...
read it

Practical Fully Dynamic Minimum Cut Algorithms
We present a practically efficient algorithm for maintaining a global mi...
read it

Tight Bounds for Online Graph Partitioning
We consider the following online optimization problem. We are given a gr...
read it

ConstantTime Dynamic Weight Approximation for Minimum Spanning Forest
We give two fully dynamic algorithms that maintain a (1+ε)approximation...
read it

A Combinatorial CutBased Algorithm for Solving Laplacian Linear Systems
Over the last two decades, a significant line of work in theoretical alg...
read it

New Techniques and FineGrained Hardness for Dynamic NearAdditive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
read it

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
read it

FullyDynamic Coresets
With input sizes becoming massive, coresets—small yet representative sum...
read it

Faster Parallel Multiterminal Cuts
We give an improved branchandbound solver for the multiterminal cut pr...
read it

Dynamic Maintenance of LowStretch Probabilistic Tree Embeddings with Applications
We give the first nontrivial fully dynamic probabilistic tree embedding...
read it

Dynamic Maintanance of LowStretch Probabilistic Tree Embeddings with Applications
We give the first nontrivial fully dynamic probabilistic tree embedding...
read it

Dynamic Matching Algorithms in Practice
In recent years, significant advances have been made in the design and a...
read it

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles
Independent set is a fundamental problem in combinatorial optimization. ...
read it

Dynamic Set Cover: Improved Amortized and WorstCase Update Time
In the dynamic minimum set cover problem, a challenge is to minimize the...
read it

An Improved Algorithm for Dynamic Set Cover
We consider the minimum set cover problem in a dynamic setting. Here, we...
read it

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
Graph coloring is a fundamental problem in computer science. We study th...
read it

Finding All Global Minimum Cuts In Practice
We present a practically efficient algorithm that finds all global minim...
read it

Faster Fully Dynamic Transitive Closure in Practice
The fully dynamic transitive closure problem asks to maintain reachabili...
read it

Upper and Lower Bounds for Fully Retroactive Graph Problems
Classic dynamic data structure problems maintain a data structure subjec...
read it

A New Deterministic Algorithm for Dynamic Set Cover
We present a deterministic dynamic algorithm for maintaining a (1+ϵ)fap...
read it

A Tree Structure For Dynamic Facility Location
We study the metric facility location problem with client insertions and...
read it

NearLinear Time Algorithms for Streett Objectives in Graphs and MDPs
The fundamental modelchecking problem, given as input a model and a spe...
read it

Quasipolynomial SetBased Symbolic Algorithms for Parity Games
Solving parity games, which are equivalent to modal μcalculus model che...
read it

SharedMemory BranchandReduce for Multiterminal Cuts
We introduce the fastest known exact algorithm for the multiterminal cut...
read it

Fully Dynamic kCenter Clustering in Doubling Metrics
In the kcenter clustering problem, we are given a set of n points in a ...
read it

ConstantTime Dynamic (Δ+1)Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
With few exceptions (namely, algorithms for maximal matching, 2approxim...
read it

Fully Dynamic SingleSource Reachability in Practice: An Experimental Study
Given a directed graph and a source vertex, the fully dynamic singlesou...
read it

Efficient Distributed Workload (Re)Embedding
Modern networked systems are increasingly reconfigurable, enabling deman...
read it

Distributed Edge Connectivity in Sublinear Time
We present the first sublineartime algorithm for a distributed message...
read it

New Amortized CellProbe Lower Bounds for Dynamic Problems
We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (F...
read it

Algorithms and Hardness for Diameter in Dynamic Graphs
The diameter, radius and eccentricities are natural graph parameters. Wh...
read it

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Many dynamic graph algorithms have an amortized update time, rather than...
read it

Sharedmemory Exact Minimum Cuts
The minimum cut problem for an undirected edgeweighted graph asks us to...
read it

Algorithms and Conditional Lower Bounds for Planning Problems
We consider planning problems for graphs, Markov decision processes (MDP...
read it

Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives
Given a model and a specification, the fundamental modelchecking proble...
read it

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
We consider the problem of dynamically maintaining (approximate) allpai...
read it

Memetic Graph Clustering
It is common knowledge that there is no single best strategy for graph c...
read it

The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
We introduce a new algorithmic framework for designing dynamic graph alg...
read it

Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter
A model of computation that is widely used in the formal analysis of rea...
read it

Dynamic Algorithms for Graph Coloring
We design fast dynamic algorithms for proper vertex and edge colorings i...
read it

Capacity Releasing Diffusion for Speed and Locality
Diffusions and related random walk procedures are of central importance ...
read it
Monika Henzinger
is this you? claim profile