121 citations · 181 across the 38 of their papers we have counts for
4 papers · 1 filter
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
Radu Curticapean, Nathan Lindzey, Jesper Nederlof
For even , the matchings connectivity matrix encodes which pairs of perfect matchings on vertices form a single cycle. Cygan et al. (STOC 2013) showed that th…
New Tools and Connections for Exponential-time Approximation
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit +2
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter , and the goal is to d…
Competitive Algorithms for Generalized k-Server in Uniform Metrics
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos +1
The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server lies in its own metric space . A reques…
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…