Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases.
Mathias WellerAnnie ChateauClément DallardRodolphe GiroudeauPublished in: Algorithmica (2018)
Keyphrases
- fixed parameter tractable
- computational problems
- computational complexity
- parameterized complexity
- special case
- optimization problems
- np hard
- np complete
- approximation algorithms
- worst case
- reasoning tasks
- fixed parameter tractability
- combinatorial problems
- global constraints
- decision problems
- exact solution
- heuristic methods
- conjunctive queries
- bounded treewidth
- combinatorial optimization
- evolutionary algorithm