62 citations · 316 across the 38 of their papers we have counts for
4 papers · 2 filters
NC Algorithms for Weighted Planar Perfect Matching and Related Problems
Piotr Sankowski
Consider a planar graph with polynomially bounded edge weight function . The main results of this paper are NC algorithms for the following problems:…
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry +3
For over a decade now we have been witnessing the success of {\em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for…
Contracting a Planar Graph Efficiently
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +3
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access…
Decremental Single-Source Reachability in Planar Digraphs
Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki +1
In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(n\log^2{n}…