1 citations · 4 across the 22 of their papers we have counts for
3 papers · 1 filter
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most i…
Fully dynamic biconnectivity in time
Jacob Holm, Wojciech Nadara, Eva Rotenberg +1
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. O…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…