2 papers
cs.DS2025
Planar Multiway Cut with Terminals on Few Faces
Sukanya Pandey, Erik Jan van Leeuwen
We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{…
cs.DM2025
Concurrency Constrained Scheduling with Tree-Like Constraints
Hans L. Bodlaender, Danny Hermelin, Erik Jan van Leeuwen
This paper investigates concurrency-constrained scheduling problems, where the objective is to construct a schedule for a set of jobs subject to concurrency restrictions. Formally,…