33 citations · 104 across the 16 of their papers we have counts for
3 papers · 1 filter
A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
Jesper Nederlof, Céline M. F. Swennenhuis, Karol Węgrzycki
In a classical scheduling problem, we are given a set of jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on identica…
A polynomial-time -approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Independent Set of Objects problem, we are given an -vertex planar graph and a family of objects, where each object is a connected subgraph…
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…