3 papers
cs.CG2019
Link Crossing Number is NP-hard
Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
cs.DS2017
The Bane of Low-Dimensionality Clustering
Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg +1
In this paper, we give a conditional lower bound of on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…
cs.DS2015
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
Vincent Cohen-Addad, Arnaud de Mesmay
Given a graph cellularly embedded on a surface of genus , a cut graph is a subgraph of such that cutting along yields a topological disk. We provide a fixed…