计算机科学

计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 51-58.doi: 10.11896/jsjkx.191100118

• 理论计算机科学 • 上一篇    下一篇

图的树分解算法及其应用

雷莹, 许道云   

  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)

PDF (PC)

715

摘要： 一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。 忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。

关键词: 树分解, CNF公式, 树宽度, 求解难度

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.

Key words: Tree decomposition, CNF formula, Tree width, Difficulty of solution-finding

中图分类号: 

  • 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 .
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发