A Linear Time Algorithm for Counting #2SAT on Series-Parallel Formulas

被引：1
|
作者：
Lopez-Medina, Marco A. [1 ]
Raymundo Marcial-Romero, J. [1 ]
De Ita-Luna, Guillermo [2 ]
Hernandez, Jose A. [1 ]
机构：
[1] UAEMex, Fac Ingn, Toluca, Mexico
[2] BUAP, Fac Ciencias Comp, Puebla, Mexico
来源：
ADVANCES IN SOFT COMPUTING, MICAI 2020, PT I | 2020年 / 12468卷
关键词：
#SAT; #2SAT; Complexity theory; Graph theory;
D O I：
10.1007/978-3-030-60884-2_33
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
An O(m + n) time algorithm is presented for counting the number of models of a two Conjunctive Normal Form Boolean Formula whose constrained graph is represented by a Series-Parallel graph, where n is the number of variables and m is the number of clauses. To the best of our knowledge, no linear time algorithm has been developed for counting in this kind of formulas.
引用
收藏
页码：437 / 447
页数：11
相关论文
共 50 条
  • [1] A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas
    Lopez, Marco A.
    Raymundo Marcial-Romero, J.
    De Ita, Guillermo
    Moyao, Yolanda
    PATTERN RECOGNITION, 2018, 10880 : 72 - 81
  • [2] Linear-Time Algorithm for Quantum 2SAT
    Arad, Itai
    Santha, Miklos
    Sundaram, Aarthi
    Zhang, Shengyu
    THEORY OF COMPUTING, 2018, 14 : 1 - 27
  • [3] Counting models for 2SAT and 3SAT formulae
    Dahllöf, V
    Jonsson, P
    Wahström, M
    THEORETICAL COMPUTER SCIENCE, 2005, 332 (1-3) : 265 - 291
  • [4] A linear time algorithm for the Hamiltonian path problem on a series-parallel graph
    Wu, QS
    Lee, RCT
    Chao, KM
    PROCEEDINGS OF THE FIFTH JOINT CONFERENCE ON INFORMATION SCIENCES, VOLS 1 AND 2, 2000, : 531 - 534
  • [5] Compact linear programs for 2SAT
    Avis, David
    Tiwary, Hans Raj
    EUROPEAN JOURNAL OF COMBINATORICS, 2019, 80 : 17 - 22
  • [6] On determining the minimum length, tree-like resolution refutation of 2SAT, and extended 2SAT formulas
    Subramani, K
    ADVANCES IN COMPUTING SCIENCE-ASIAN 2002: INTERNET-COMPUTING AND MODELING, GRID COMPUTING, PEER-TO-PEER COMPUTING, AND CLUSTER COMPUTING, 2002, 2550 : 57 - 65
  • [7] Recognizing Series-Parallel Matrices in Linear Time
    Walter, Matthias
    INFORMS JOURNAL ON COMPUTING, 2023, 35 (06) : 1404 - 1418
  • [8] LINEAR-TIME ALGORITHM FOR NETWORK SYNTHESIS PROBLEM IN A SERIES-PARALLEL GRAPH
    HOJATI, M
    UTILITAS MATHEMATICA, 1995, 48 : 97 - 105
  • [9] A linear-time certifying algorithm for recognizing generalized series-parallel graphs
    Chin, Francis Y. L.
    Ting, Hing-Fung
    Tsin, Yung H.
    Zhang, Yong
    DISCRETE APPLIED MATHEMATICS, 2023, 325 : 152 - 171
  • [10] A LINEAR ALGORITHM FOR THE DOMINATION NUMBER OF A SERIES-PARALLEL GRAPH
    KIKUNO, T
    YOSHIDA, N
    KAKUDA, Y
    DISCRETE APPLIED MATHEMATICS, 1983, 5 (03) : 299 - 311
12345