Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete.
Osamu MaruyamaSatoru MiyanoPublished in: MFCS (1995)
Keyphrases
- bounded degree
- np complete
- bounded treewidth
- graph theoretic
- randomly generated
- satisfiability problem
- conjunctive queries
- np hard
- computational complexity
- constraint satisfaction problems
- random walk
- polynomial time complexity
- probabilistic inference
- phase transition
- bayesian networks
- boolean functions
- relational learning
- conp complete
- objective function