Open AccessAlgorithm to Count the Number of Signed Paths in an Electrical Network via Boolean Formulas
Author(s) -
Guillermo De Ita Luna,
Helena Gómez,
Belem Merino
Publication year - 2012
Publication title -
acta universitaria
Language(s) - English
Resource type - Journals
eISSN - 2007-9621
pISSN - 0188-6266
DOI - 10.15174/au.2012.344
Subject(s) - node (physics) , topology (electrical circuits) , boolean network , discrete mathematics , set (abstract data type) , charge (physics) , network topology , mathematics , computer science , graph , line (geometry) , boolean function , algorithm , combinatorics , computer network , physics , geometry , quantum mechanics , programming language
This article presents a practical method to count the different signed paths which maintain an electric charge on each one of the lines of an electrical network. We assume that there is just one charge (positive or negative) on each network node. We model the problem of counting the signed paths via the #2SAT problem. The #2SAT problem consists on counting models of Boolean formulas in two conjunctive forms. Our method is based on the topology of the graph representing the electrical network and from which we get its Boolean formula in two conjunctive form. A set of recurrence equations are applied, starting from the terminal nodes up to the root node of the network. Such recurrence equations allow us to compute #2SAT for the formula associated to the electrical network. The computed value (#2SAT) represents the different ways to keep charge on all line of the electrical network.