Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees
| Autor: | Martin Charles Golumbic, Udi Rotics, Aviad Mintz |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Discrete mathematics
k-trees Applied Mathematics media_common.quotation_subject Subroutine Graph partition computer.software_genre Cographs Combinatorics Factoring Read-once functions Discrete Mathematics and Combinatorics Computer Aided Design Cograph Boolean functions Normal functions Boolean function Time complexity computer Normality Mathematics media_common |
| Zdroj: | Discrete Applied Mathematics. 154:1465-1477 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2005.09.016 |
| Popis: | An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195–198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131–153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality.For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read 2k function and a read 2k formula for F can be obtained in polynomial time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect