1 citations · 2 across the 6 of their papers we have counts for
6 papers
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{…
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,…
The Parameterised Complexity of Integer Multicommodity Flow
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen +2
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths…
Approximation and parameterized algorithms for geometric independent set with shrinking
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappin…
Parameterized Complexity Dichotomy for Steiner Multicut
Karl Bringmann, Danny Hermelin, Matthias Mnich +1
The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt V(G) of size at most p, and an integer k, whether there is a set S of at most k…
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,..…