3 papers
cs.CG2026
Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
Mark de Berg, Bart M. P. Jansen, Jeroen S. K. Lamme
We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of constant-complexity objects in the plane. We prove SSSP can…
cs.CG2025
Star-Based Separators for Intersection Graphs of -Colored Pseudo-Segments
M. de Berg, B. M. P. Jansen, J. S. K. Lamme
The Planar Separator Theorem, which states that any planar graph has a separator consisting of nodes whose removal partitions into compone…
cs.DS2025
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph and integers and , the standard…