Title :
A maximum clique derivation algorithm for simplification of incompletely specified machines
Author :
Hashizume, Masaki ; Tamesada, Takeomi ; Sakamoto, Akio
Author_Institution :
Fac. of Eng., Tokushima Univ., Japan
fDate :
30 May-2 Jun 1994
Abstract :
In this paper, derivation problems of maximum cliques are discussed, which take place in simplification processes of incompletely specified machines. In many cases, graphs consisting of a lot of edges are generated in the processes. Thus, for many combinations of the edges, it should be examined whether a clique is made of them. Therefore, it is impossible to derive the maximum cliques within a reasonable time. This paper presents a new algorithm to derive all the maximum cliques, which is more suitable for the derivation of maximum cliques of the undirected graphs generated in the simplification processes
Keywords :
computational complexity; graph theory; logic CAD; sequential machines; incompletely specified machines; maximum clique derivation algorithm; simplification processes; undirected graphs; Circuit synthesis; Heuristic algorithms; Minimization; NP-complete problem; Sequential circuits;
Conference_Titel :
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location :
London
Print_ISBN :
0-7803-1915-X
DOI :
10.1109/ISCAS.1994.408788
