Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.

Vincent Cohen-Addad Éric Colin de Verdière Dániel Marx Arnaud de Mesmay

Published in: SoCG (2019)

Keyphrases

lower bound
upper bound
optimization problems
branch and bound algorithm
np hard
worst case
objective function
data structure
special case
np complete
random instances