Factoring Boolean functions using graph partitioning

DOI10.1016/J.DAM.2005.02.007MaRDI QIDQ2387436zbMATH OpenOpenAlexFDO

Authors Aviad Mintz, Martin Charles Golumbic

Publication date 2 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.02.007

zbMATH Keywords

Factoring Boolean functionsGraph partitioningLogic synthesis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Factorization of Boolean polynomials: parallel algorithms and experimental evaluation
• Graph-Based Algorithms for Boolean Function Manipulation
• Factoring a graph in polynomial time
• scientific article; zbMATH DE number 1287928
• A graph-theoretic method to define any Boolean operation on partitions
• scientific article; zbMATH DE number 1294417
• scientific article; zbMATH DE number 5064167
• scientific article; zbMATH DE number 512939
• Partitioning 1-variable Boolean functions for various classification ofn-variable Boolean functions
• Factorizing Boolean matrices using formal concepts and iterative usage of essential entries

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• An Efficient Heuristic Procedure for Partitioning Graphs
• Factoring logic functions
• scientific article; zbMATH DE number 991436 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3974977 (Why is no real title available?)
• scientific article; zbMATH DE number 3545568 (Why is no real title available?)
• scientific article; zbMATH DE number 219938 (Why is no real title available?)
• scientific article; zbMATH DE number 918600 (Why is no real title available?)
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Fanout Structure of Switching Functions
• Topics in Intersection Graph Theory

Cited in

(14)

• Factorization of Boolean polynomials: parallel algorithms and experimental evaluation
• A compositional approach to probabilistic knowledge compilation
• On lengths of edge-labeled graph expressions
• Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs
• Estimation of expressions' complexities for two-terminal directed acyclic graphs
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Partitioning 1-variable Boolean functions for various classification ofn-variable Boolean functions
• Factoring logic functions
• scientific article; zbMATH DE number 5239161 (Why is no real title available?)
• Partially unate Boolean functions: properties of their sum-of-products representations
• Algebraic expressions of grid graphs with diagonal edges
• Complexity minimization in rule-based category learning: revising the catalog of Boolean concepts and evidence for non-minimal rules
• An improvement on the complexity of factoring read-once Boolean functions

This page was built for publication: Factoring Boolean functions using graph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2387436)