Computer Science ›› 2020, Vol. 47 ›› Issue (5): 51-58.doi: 10.11896/jsjkx.191100118
Special Issue: Theoretical Computer Scinece
• Theoretical Computer Science • Previous Articles Next Articles
LEI Ying, XU Dao-yun
CLC Number:
| [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] | HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30. |
| [2] | SONG Jing-qi, LIU Hui and ZHANG Cai-ming. Medical Image Super Resolution Reconstruction Based on Adaptive Patch Clustering [J]. Computer Science, 2016, 43(Z11): 210-214. |
| [3] | ZHANG Ming-ming and XU Dao-yun. Phase Transition Phenomenon of Regular 3-SAT Problem [J]. Computer Science, 2016, 43(4): 33-36. |
| [4] | . Tree Decomposition and its Applications in Algorithms:Survey [J]. Computer Science, 2012, 39(3): 14-18. |
|
||
Home