Title :
On maximal graphs with a k-clique
Author :
Koranne, S. ; Limaye, P. ; Sharma, R.
Author_Institution :
VLSI Design Tools & Tech., Indian Inst. of Technol., Delhi, India
Abstract :
In this paper we present a novel approach towards constructing a maximal edge graph with a k-clique. The problem is NP-hard and we describe an efficient heuristic to arrive at an approximate solution. As the main contribution of this paper, we show that the above problem can be easily reduced to the problem of graph embedding with constraints. We also analyze the complexity of our method. This method finds application in many important fields of VLSI CAD, job scheduling and operations research
Keywords :
VLSI; circuit CAD; circuit optimisation; computational complexity; graph theory; network topology; NP-hard problem; VLSI CAD; complexity; constraints; efficient heuristic; graph embedding; job scheduling; k-clique; maximal edge graph; maximal graphs; operations research; Constraint optimization; Consumer electronics; Cost function; Instruments; Operations research; Optimization methods; Routing; Testing; Very large scale integration;
Conference_Titel :
Electronics, Circuits and Systems, 1999. Proceedings of ICECS '99. The 6th IEEE International Conference on
Conference_Location :
Pafos
Print_ISBN :
0-7803-5682-9
DOI :
10.1109/ICECS.1999.814434
