First Advisor

Marek A. Perkowski

Term of Graduation

Spring 1997

Date of Publication


Document Type


Degree Name

Master of Science (M.S.) in Electrical and Computer Engineering


Electrical Engineering




Decomposition method, Mappings (Mathematics), Map-coloring problem



Physical Description

1 online resource (viii, 142 pages)


Finding the column multiplicity in Functional Decomposition has been known to be one of the most important problems to be solved in the process of functional decomposition of discrete functions. A lot of research has been done in this field with many new heuristics generated to find the column multiplicity, but there has not been an evaluation of the algorithms on the kinds of graphs that occur in decomposition and whether having an exact method to calculate the column multiplicity is useful from the overall design goals.The intent of this thesis was to investigate the column multiplicity problem, in order to find out how different heuristic algorithms compare with an exact algorithm for finding the column multiplicity, and to find out if an exact graph coloring is actually required or not.

In order to investigate this problem of column multiplicity in functional decomposition, two graph coloring programs, and a multi-coloring program were written: one of the graph coloring programs is an exact graph coloring, the other graph coloring program and the multi-coloring program are both based on heuristic algorithms. The two graph coloring programs have been compared in this thesis on randomly generated graphs. These programs were incorporated into the multi-valued decomposer of functions and relations MVGUD which was developed at Portland State University. Extensive testing of MVGUD with these graph coloring and multi-coloring programs has been done in this thesis. MVGUD was tested on both circuit benchmarks and on machine learning benchmarks.


In Copyright. URI:

This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).


If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to and include clear identification of the work, preferably with URL.

Persistent Identifier