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

LOPEZ MEDINA, MARCO ANTONIO; MARCIAL ROMERO, JOSE RAYMUNDO; DE ITA LUNA, GUILLERMO; Hernández Servín, José Antonio

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

LOPEZ MEDINA, MARCO ANTONIO; MARCIAL ROMERO, JOSE RAYMUNDO; DE ITA LUNA, GUILLERMO; Hernández Servín, José Antonio

URI: http://hdl.handle.net/20.500.11799/110146

Fecha: 2020

Resumen:

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.

Descripción:

Capítulo de libro

Mostrar el registro completo del objeto digital

Ficheros en el objeto digital

Nombre: 2020_Chapter_ALin ...

Tamaño: 371.5Kb

Formato: PDF

Ver documento

Este ítem aparece en la(s) siguiente(s) colección(ones)

Conacyt [10019]
Científica [308]

Visualización del Documento

Título
A Linear Time Algorithm for Counting #2SAT on Series-Parallel Formulas
Autor
LOPEZ MEDINA, MARCO ANTONIO
MARCIAL ROMERO, JOSE RAYMUNDO
DE ITA LUNA, GUILLERMO
Hernández Servín, José Antonio
Fecha de publicación
2020
Editor
Martínez-Villaseñor L., Herrera-Alcántara O., Ponce H., Castro-Espinoza F.A.
Tipo de documento
Capítulo de Libro
Palabras clave
Graph Decomposition
Enumerative Algorithm
Counting models

Los documentos depositados en el Repositorio Institucional de la Universidad Autónoma del Estado de México se encuentran a disposición en Acceso Abierto bajo la licencia Creative Commons: Atribución-NoComercial-SinDerivar 4.0 Internacional (CC BY-NC-ND 4.0)