Recognizing Union-Find trees is NP-complete.
Kitti GelleSzabolcs IvánPublished in: Inf. Process. Lett. (2018)
Keyphrases
- np complete
- randomly generated
- np hard
- decision trees
- satisfiability problem
- constraint satisfaction problems
- tree structure
- conjunctive queries
- computational complexity
- pspace complete
- phase transition
- automatic recognition
- tree models
- polynomially solvable
- polynomial time complexity
- tree structures
- special case
- np complete problems
- scheduling problem
- data complexity
- cnf formula
- tree construction