2 papers
cs.DS2026
Efficient Parallel Algorithms for Hypergraph Matching
Henrik Reinstädtler, Christian Schulz, Nodari Sitchinava +1
We present efficient parallel algorithms for computing maximal matchings in hypergraphs. Our algorithm finds locally maximal edges in the hypergraph and adds them in parallel to th…
cs.DS2026
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
Peyman Afshani, Gerth Stølting Brodal, Nodari Sitchinava
We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is de…