Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.

Jacob Focke Florian Hörsch Shaohua Li Dániel Marx

Published in: SoCG (2024)

Keyphrases

decision problems
problems involving
computational issues
computational complexity
np complete
polynomial hierarchy
data mining
computational cost
optimization problems
graphical models
combinatorial optimization
lead time
space complexity
spanning tree
np hardness
series parallel