Portland State University. Department of Electrical and Computer Engineering
Marek A. Perkowski
Term of Graduation
Date of Publication
Master of Science (M.S.) in Electrical and Computer Engineering
Electrical and Computer Engineering
Decomposition method, Mappings (Mathematics), Map-coloring problem
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: http://rightsstatements.org/vocab/InC/1.0/
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).
Malvi, Rahul, "The Column Multiplicity Problem in Decomposition of Functions and Relations" (1997). Dissertations and Theses. Paper 5830.