The Depth-Restricted Rectilinear Steiner Arborescence Problem is NP-complete.
Jens MaßbergPublished in: CoRR (2015)
Keyphrases
- np complete
- randomly generated
- satisfiability problem
- np hard
- constraint satisfaction problems
- computational complexity
- np complete problems
- bounded treewidth
- phase transition
- pspace complete
- depth information
- data complexity
- depth map
- search algorithm
- minimum weight
- arbitrary shaped
- conjunctive queries
- steiner tree