121 citations · 181 across the 38 of their papers we have counts for
3 papers · 1 filter
Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen
The Planar Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a…
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Bart M. P. Jansen, Jesper Nederlof
Computing the smallest number such that the vertices of a given graph can be properly -colored is one of the oldest and most fundamental problems in combinatorial optimizati…
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell +1
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-ti…