19 citations · 54 across the 16 of their papers we have counts for
4 papers · 1 filter
Independent Sets in Vertex-Arrival Streams
Graham Cormode, Jacques Dark, Christian Konrad
We consider the classic maximal and maximum independent set problems in three models of graph streams: In the edge-arrival model we see a stream of edges which collectively define…
Detecting cliques in CONGEST networks
Artur Czumaj, Christian Konrad
The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given…
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Christian Konrad, Viktor Zamaraev
We give deterministic distributed -approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algori…
MIS in the Congested Clique Model in Rounds
Christian Konrad
We give a maximal independent set (MIS) algorithm that runs in rounds in the congested clique model, where is the maximum degree of the input graph. This impro…