Rectangular Partition is Polynomial in Two Dimensions but NP-Complete in Three.
Victor J. DielissenAnne KaldewaijPublished in: Inf. Process. Lett. (1991)
Keyphrases
- np complete
- randomly generated
- satisfiability problem
- np hard
- constraint satisfaction problems
- fixed parameter tractable
- pspace complete
- computational complexity
- conjunctive queries
- multiple dimensions
- np complete problems
- polynomial time complexity
- integer programming
- data complexity
- low order
- packing problem
- phase transition
- branch and bound algorithm
- upper bound