Éric Colin de Verdière

activity

20082025

most citedDeciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational Loop Theorem

1 citations · 2 across the 7 of their papers we have counts for

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2019★ 1 cited

Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

Sergio Cabello, Éric Colin de Verdière

In the Minimum Installation Path problem, we are given a graph $G$ with edge weights $w (.)$ and two vertices $s, t$ of $G$ . We want to assign a non-negative power $p (v)$ to each ver…

cs.CC2019

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx +1

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded gra…