19 citations · 54 across the 16 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017★ 3 cited
Independent Set Size Approximation in Graph Streams
Graham Cormode, Jacques Dark, Christian Konrad
We study the problem of estimating the size of independent sets in a graph defined by a stream of edges. Our approach relies on the Caro-Wei bound, which expresses the desired…
cs.DS2017★ 2 cited
Preemptive Online Partitioning of Sequences
Christian Konrad, Tigran Tonoyan
Online algorithms process their inputs piece by piece, taking irrevocable decisions for each data item. This model is too restrictive for most partitioning problems, since data tha…