• 理论计算机科学 •

### 图的树分解算法及其应用

1. 贵州大学计算机科学与技术学院 贵阳550025
• 收稿日期:2019-11-15 出版日期:2020-05-15 发布日期:2020-05-19
• 通讯作者: 许道云(dyxu@gzu.edu.cn)
• 作者简介:1152586591@qq.com
• 基金资助:
国家自然科学基金(61762019,61862051)

### Tree Decomposition Algorithm of Graph and Its Application

LEI Ying, XU Dao-yun

1. College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
• Received:2019-11-15 Online:2020-05-15 Published:2020-05-19
• About author:LEI Ying,born in 1992,postgraduate,is a member of China Computer Federation.Her main research interest is include algorithm design and analysis.
XU Dao-yun,born in 1959,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include computability and computational complexity.
• Supported by:
This work was supported by the National Natural Science Foundation of China(61762019, 61862051)

Abstract: A tree decomposition of the graph G=(V,E) refers to taking a subset of the node set V as a node of the tree T,to make the intersection of the two endpoints on any path of T included in any node on the path.The number of elements of the mini-mum (node) corresponding subset on T minus 1 is defined as the width of the decomposition tree T,and the tree width of the graph G is defined by the tree width of the decomposition tree T with the smallest width.The CNF formula F can be represented by a bipartite graph G=(V∪C,E) (factor graph of the formula),where the variable node set V corresponds to the variable set,and the clause node set C corresponds to the clause set in the formula F.The positive (negative) occurrence of the element in the clause is represented by the real (virtual) side.In order to study the bipartite graph,the symbols on the edges of the formula factor graph are ignored.This paper studies the tree decomposition algorithm of graphs and applies the tree decomposition algorithm to the factor graph tree decomposition of CNF formula,aiming to explore the relationship between the tree width of the formula factor graph and the difficulty of the solution-finding through experiments.

• TP301
 [1] BODLAENDER H L,KOSTER A M C A.Treewidth computations II.Lower bounds[J].Information and Computation,2011,209(7):1103-1119. [2] HAMMERL T,MUSLIU N,SCHAFHAUSER W.Metaheuristic algorithms and tree decomposition[M]//Springer Handbook of Computational Intelligence.Berlin:Springer,2015:1255-1270. [3] BODLAENDER H L.A linear-time algorithm for finding tree-decompositions of small treewidth[J].SIAM Journal on Computing,1996,25(6):1305-1317. [4] COOK S A.The complexity of theorem-proving procedures[C]//Proceedings of the Third Annual ACM Symposium on Theory of Computing.ACM,1971:151-158. [5] ABSEHER M,DUSBERGER F.Improving the efficiency of dynamic program ming on tree decompositions via machine learning[J].Journal of Artificial IntelliIgence Research,2017,58:829-858. [6] TELLE J A,ROSKUROWSKI A.Algorithms for vertex partitioning problems on partial k-trees[J].SIAM Journal on Discrete Mathematics,1997,10(4)529-550. [7] BLIEM B,MOLDOVAN M.The Impact of Treewidth on ASP Grounding and Solving[C]//Twenty-sixth International Joint Conference on Artificial Intelligence.Melbourne,Australia,2017:852-858. [8] ZHANG N L.Computational properties of two exact algorithms for Bayesian networks[J].Applied Intelligence,1998,9(2):173-183. [9] DUBOIS O,MONASSON R,SELMAN B,et al.Phase transitions in combinatorial problems[J].Theoretical Computer Science,2001(265):1-2. [10] XU K,LI W.Exact phase transitions in random constraint satisfaction problems[J].Journal of Artificial Intelligence Research,2000,12(1):93-103. [11] SZEIDER S.Generalizations of matched CNF formulas[J].Annals of Mathematics and Artificial Intelligence,2005,43(1/2/3/4):223-238. [12] SZEIDER S.Matched formulas and backdoor sets[C]//Interna-tional Conference on Theory and Applications of Satisfiability Testing.Berlin:Springer,2007:94-99. [13] SURYNEK P.Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs[C]//2014 IEEE 26th International Conference on Tools with Artificial Intelligence.IEEE,2014:875-882. [14] XU D Y,WANG X F.A Regular NP-Complete problem and its inapproximability[J].Journal of Frontiers of Computer Science and Technology,2013,7(8):691-697. [15] KRISHNAMURTHY S,SAHOO S.Balanced k-satisfiabilityand biased random k-satisfiability on trees[J].Physical Review E,2013,87(4):042130. [16] CHEN J.Parameterized Computation and Complexity:A NewApproach Dealing with NP-Hardness[J].Journal of Computer Science and Technology,2005,20(1):18-25. [17] RAIBLE D,FERNAU H.A new upper bound for Max-2-SAT:A graph-theoretic approach[C]//International Symposium on Mathematical Foundations of Computer Science.Berlin:Springer,2008(8):551-562. [18] ROBERTSON N,SEYMOUR P D.Graph minors.X.Obstructions to tree-decomposition[J].Journal of Combinatorial Theory(Series B),1991,52(2):153-190. [19] GOTTLOB G,LEONE N,SCARCELLO F.A comparison ofstructural CSP decomposition methods[J].Artificial Intelligence,2000,124(2):243-282. [20] CHEN H B.Quantified Constraint Satisfaction and BoundedTreewidth.[C]// Eureopean Conference on Artificial Intelligence.DBLP,2004:161-165. [21] BORDEAUX L,CADOLI M,MANCINI T.CSP properties for quantified constraints:Definitions and complexity[C]//AAAI.2005:360-365. [22] WANG X F,XU D Y,WEI L.Convergence of Warning Propagation Algorithms for Random Satisfiable Instances[J].Journal of Software,2013,24(1):1-11. [23] XU D Y,DENG T Y,ZHANG Q S.k-LSAT is NP-Complete for k≥3[J].Journal of Software,2008(3):511-521. [24] PORSCHEN S,SPECKENMEYER E,RANDERATH B.Onlinear CNF formulas[M]//Proc.of the 19th Int'l Conf.on Theory and Applications of Satisfiability Testing-SAT 2006.New York:Springer-Verlag,2006:212-225. [25] PORSCHEN S,SPECKENMEYER E.NP-Completeness ofSAT for restricted linear formulas classes[C]//Proc.of the Guangzhou Symp.& On Satisfiability in Logic-Based Modeling.2006:111-123.
 [1] 宋俊花, 魏欧. 基于线性时间算法的故障树模块扩展分解方法[J]. 计算机科学, 2019, 46(1): 226-231. [2] 宋景琦,刘慧,张彩明. 基于自适应块聚类的医学图像超分辨重建[J]. 计算机科学, 2016, 43(Z11): 210-214. [3] 张明明,许道云. 正则3-SAT问题的相变现象[J]. 计算机科学, 2016, 43(4): 33-36. [4] 高文宇，李绍华. 图的树分解及其算法应用研究进展[J]. 计算机科学, 2012, 39(3): 14-18.
Viewed
Full text

Abstract

Cited

Shared
Discussed
 [1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 . [2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 . [3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 . [4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 . [5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 . [6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 . [7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 . [8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 . [9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 . [10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .