The rectilinear Steiner arborescence problem is NP-complete.
Weiping ShiChen SuPublished in: SODA (2000)
Keyphrases
- np complete
- np hard
- randomly generated
- constraint satisfaction problems
- np complete problems
- computational complexity
- conjunctive queries
- polynomial time complexity
- minimum weight
- steiner tree
- polynomially solvable
- database
- satisfiability problem
- arbitrary shaped
- ground plane
- pspace complete
- phase transition
- data complexity
- scheduling problem
- data exchange
- query language
- dynamic programming
- databases