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 条
  • [31] A polynomial time approximation scheme for dense MIN 2SAT
    Bazgan, C
    de la Vega, WF
    FUNDAMENTALS OF COMPUTATION THEORY, 1999, 1684 : 91 - 99
  • [32] Linear algorithm for finding list edge-colorings of series-parallel graphs
    Fujino, T
    Isobe, S
    Zhou, X
    Nishizeki, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (02) : 186 - 190
  • [33] EXPLICIT FORMULAS FOR CHROMATIC POLYNOMIALS OF SOME SERIES-PARALLEL GRAPHS
    Lerner, E. Y.
    Mukhamedjanova, S. A.
    UCHENYE ZAPISKI KAZANSKOGO UNIVERSITETA-SERIYA FIZIKO-MATEMATICHESKIE NAUKI, 2018, 160 (02): : 339 - 349
  • [34] On mixed linear layouts of series-parallel graphs
    Angelini, Patrizio
    Bekos, Michael A.
    Kindermann, Philipp
    Mchedlidze, Tamara
    THEORETICAL COMPUTER SCIENCE, 2022, 936 : 129 - 138
  • [35] Minimum Linear Arrangement of Series-Parallel Graphs
    Eikel, Martina
    Scheideler, Christian
    Setzer, Alexander
    APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2014, 2015, 8952 : 168 - 180
  • [36] A POLYNOMIAL-TIME ALGORITHM FOR SUBGRAPH ISOMORPHISM OF 2-CONNECTED SERIES-PARALLEL GRAPHS
    LINGAS, A
    SYSLO, MM
    LECTURE NOTES IN COMPUTER SCIENCE, 1988, 317 : 394 - 409
  • [37] Exact counting of Euler tours for generalized series-parallel graphs
    Chebolu, Prasad
    Cryan, Mary
    Martin, Russell
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 10 (01) : 110 - 122
  • [38] A Linear Time Algorithm for Quantum 2-SAT
    de Beaudrap, Niel
    Gharibian, Sevag
    31ST CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2016), 2016, 50
  • [39] A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs
    Nakayama, Shin-ichi
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2019, E102D (04) : 826 - 835
  • [40] 2-MACHINE MAXIMUM FLOW TIME PROBLEM WITH SERIES-PARALLEL PRECEDENCE CONSTRAINTS - ALGORITHM AND EXTENSIONS
    MONMA, CL
    OPERATIONS RESEARCH, 1979, 27 (04) : 792 - 798
12345