2 papers
cs.DS2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
Rajesh Chitnis, Andreas Emil Feldmann, MohammadTaghi Hajiaghayi +1
(see paper for full abstract) Given a vertex-weighted directed graph and a set of terminals, the objective of the SCSS problem is to find…
cs.CG2018
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak +2
We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to int…