Embedding Trees in a Hypercube is NP-Complete.
Alan WagnerDerek G. CorneilPublished in: SIAM J. Comput. (1990)
Keyphrases
- np complete
- randomly generated
- np hard
- satisfiability problem
- computational complexity
- constraint satisfaction problems
- pspace complete
- data complexity
- parallel algorithm
- bounded treewidth
- databases
- tree structure
- conjunctive queries
- nonlinear dimensionality reduction
- phase transition
- tree automata
- tree structures
- vector space
- conp complete
- data embedding
- master slave
- graph embedding
- watermarking algorithm
- decision trees