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 条
  • [41] Transfer Time Suppressor with Series-Parallel Connection
    Arias, M.
    Hernando, M. M.
    Lamar, D. G.
    Rodriguez, A.
    Fernandez, A.
    APEC: 2009 IEEE APPLIED POWER ELECTRONICS CONFERENCE AND EXPOSITION, VOLS 1- 4, 2009, : 1615 - 1621
  • [42] An NC parallel algorithm for edge-coloring series-parallel multigraphs
    Zhou, X
    Suzuki, H
    Nishizeki, T
    JOURNAL OF ALGORITHMS, 1997, 23 (02) : 359 - 374
  • [43] Identification of series-parallel systems composed of linear and nonlinear blocks
    Brouri, A.
    Giri, F.
    INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING, 2023, 37 (08) : 2021 - 2040
  • [44] Base polytopes of series-parallel posets: Linear description and optimization
    Schrader, R
    Schulz, AS
    Wambach, G
    MATHEMATICAL PROGRAMMING, 1998, 82 (1-2) : 159 - 173
  • [45] Base polytopes of series-parallel posets: Linear description and optimization
    Inst. Informatik Zentrum P., Universität zu Köln, Weyertal 86-90, D-50931 Köln, Germany
    不详
    Math Program Ser B, 1-2 (159-173):
  • [46] Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets
    Bodini, Olivier
    Dien, Matthieu
    Genitrini, Antoine
    Peschanski, Frederic
    COMPUTER SCIENCE - THEORY AND APPLICATIONS (CSR 2017), 2017, 10304 : 71 - 84
  • [47] SERIES-PARALLEL COMPOSITION OF GREEDY LINEAR-PROGRAMMING PROBLEMS
    BEIN, WW
    BRUCKER, P
    HOFFMAN, AJ
    MATHEMATICAL PROGRAMMING, 1993, 62 (01) : 1 - 14
  • [48] Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time
    Didimo, Walter
    Kaufmann, Michael
    Liotta, Giuseppe
    Ortali, Giacomo
    ALGORITHMICA, 2023, 85 (09) : 2605 - 2666
  • [49] SERIES-PARALLEL GROUNDED 2-PORTS
    FIALKOW, A
    QUARTERLY OF APPLIED MATHEMATICS, 1966, 24 (03) : 195 - &
  • [50] AN EFFICIENT ALGORITHM FOR EDGE-COLORING SERIES-PARALLEL MULTIGRAPHS
    ZHOU, X
    NAKANO, S
    SUZUKI, H
    NISHIZEKI, T
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 583 : 516 - 529
12345