Published In

Proceedings of the 3rd International Workshop Boolean Problems

Document Type

Conference Proceeding

Publication Date



Computer algorithims, Quantum electronics, Logic circuits -- Design and construction


Finding column multiplicity index is one of important component processes in functional decomposition of discrete functions for circuit design and especially Data Mining applications. How important it is to solve this problem exactly from the point of view of the minimum complexity of decomposition, and related to it error in Machine Learning type of applications? In order to investigate this problem we wrote two graph coloring programs: exact program EXOC and approximate program DOM (DOM cab give provably exact results on some types of graphs). These programs were next incorporated into the multi-valued decomposer of functions and relations NVGUD. Extensive testing of MVGUD with these programs has been performed on various kinds of data. Based on these tests we demonstrated that exact graph coloring is not necessary for high-quality functional decomposers, especially in Data Mining applications, giving thus another argument that efficient and effective Machine Learning approach based on decomposition is possible.


This is the author's version of a paper which was subsequently published as: Malvi, R., Perkowski, M., & Jozwiak, L. (1998). Exact Graph Coloring for Functional Decomposition: Do we Need it?. Proc. 3rd Int. Work. Boolean Problems, 1-10.

Persistent Identifier