We develop the first parallel graph coloring heuristics with strong theoretical guarantees on
work and depth and coloring quality. The key idea is to design a relaxation of the vertex …

Maintaining a k-core decomposition quickly in a dynamic graph has important applications
in network analysis. The main challenge for designing efficient exact algorithms is that a …

We consider the problem of maintaining a (1+ ɛ)∆-edge coloring in a dynamic graph G with
n nodes and maximum degree at most Δ. The state-of-the-art update time is O ɛ (polylog …

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph,
such that the maximum out-degree is bounded. On one hand, we show how to orient the …

Submodular maximization under matroid and cardinality constraints are classical problems
with a wide range of applications in machine learning, auction theory, and combinatorial …

The densest subgraph problem has received significant attention, both in theory and in
practice, due to its applications in problems such as community detection, social network …

The problem of (Δ+ 1)-vertex coloring a graph of maximum degree Δ has been extremely
well studied over the years in various settings and models. Surprisingly, for the dynamic …

We study the problem of chasing positive bodies in 1: given a sequence of bodies
K_t=\left{x^t∈R_+^n∣C^tx^t≧1,P^tx^t≦1\right\} revealed online, where C^t and P^t are …

We study the problem of coloring a given graph using a small number of colors in several
well-established models of computation for big data. These include the data streaming …

We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time
per update that maintains a proper (Δ+ 1)-vertex coloring of a graph with maximum degree …