4 papers
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
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…
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…
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…