4 citations · 9 across the 7 of their papers we have counts for
8 papers
Improved Dynamic Colouring of Sparse Graphs
Aleksander B. G. Christiansen, Krzysztof D. Nowicki, Eva Rotenberg
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are com…
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
Krzysztof Nowicki, Krzysztof Onak
We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can e…
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
In this paper, we show that the Minimum Spanning Tree problem can be solved \emph{deterministically}, in rounds of the model…
Faster Algorithms for Edge Connectivity via Random -Out Contractions
Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each verte…
Random Sampling Applied to the MST Problem in the Node Congested Clique Model
Krzysztof Nowicki
The Congested Clique model proposed by Lotker et al.[SICOMP'05] was introduced in order to provide a simple abstraction for overlay networks. Congested Clique is a model of distrib…
MST in O(1) Rounds of the Congested Clique
Tomasz Jurdzinski, Krzysztof Nowicki
We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in O(1) rounds, with high probability, in the Congested Clique model. The input g…
MSF and Connectivity in Limited Variants of the Congested Clique
Tomasz Jurdzinski, Krzysztof Nowicki
The congested clique is a synchronous, message-passing model of distributed computing in which each computational unit (node) in each round can send message of O(log n) bits to eac…
Parallel multiple selection by regular sampling
Krzysztof Nowicki
In this paper we present a deterministic parallel algorithm solving the multiple selection problem in congested clique model. In this problem for given set of elements S and a set…