%0 Journal Article
%A LI Congcong
%A LIU Jinglei
%T Generating CP-nets with bounded tree width based on Dandelion code
%D 2021
%R 10.11772/j.issn.1001-9081.2020060972
%J Journal of Computer Applications
%P 112-120
%V 41
%N 1
%X Aiming at the problem of high time complexity of Conditional Preference networks (CP-nets) graph model in reasoning computation, a Generating CP-nets with Bounded Tree Width based on Dandelion code (BTW-CP-nets Gen) algorithm was proposed. First, through the principle of bidirectional mapping between Dandelion code and tree structure with tree width *k* (*k*-tree), the decoding and encoding algorithms between Dandelion code and *k*-tree were derived to realize the one-to-one mapping between code and tree structure. Second, the *k*-tree was used to constrain the tree width of CP-nets structure, and the *k*-tree feature tree was used to obtain the directed acyclic graph structure of CP-nets. Finally, the bijection of discrete multi-valued functions was used to calculate the conditional preference table of each CP-nets node, and the dominant query test was executed to the generated bounded tree-width CP-nets. Theoretical analysis and experimental data show that, compared with the Pruffer code generating *k*-tree (Pruffer code) algorithm, BTW-CP-nets Gen algorithm has the running time on generating simple and complex structures reduced by 21.1% and 30.5% respectively,and the node traversal ratio of the graph model generated by BTW-CP-nets Gen in the dominant query is 18.48% and 29.03% higher on simple structure and complex structure respectively; the smaller the time consumed by BTW-CP-nets Gen algorithm, the higher the traversal node ratio of the dominant query. It can be seen that BTW-CP-nets Gen algorithm can effectively improve the algorithm efficiency in graph model reasoning.
%U http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2020060972