activity
20162026
most citedGraph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

2 citations · 2 across the 5 of their papers we have counts for

collaborators
Showing 2021Show all

2 papers · 1 filter

cs.DS2021

Adversarially Robust Coloring for Graph Streams

Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may…

cs.DS2021

Vertex Ordering Problems in Directed Graph Streams

Amit Chakrabarti, Prantar Ghosh, Andrew McGregor +1

We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sort…