Search Strategies to Solve the Complex-Triangle Elimination (CTE) Problem

Abstract

This paper addresses the Complex-Triangle Elimination (CTE) problem of rectangular dualization approach in VLSI floor-planning. Rectangular dualization, where each module is realized as a rectangular area, is an important approach in VLSI floor-planning. It is known that if the input adjacency graph contains a complex triangle, i.e., a cycle of three edges that is not a face, then its rectangular dual does not exist. Elimination of complex triangles, therefore, becomes essential before constructing a floor plan. There are two versions of the CTE problem—that of weighted adjacency graphs, and of unweighted adjacency graphs. The weighted CTE problem is known to be NP-complete. Recently it has been proved that the unweighted CTE problem is also NP-complete [1]. In this paper we first present a greedy heuristic algorithm to solve the unweighted CTE problem. We then show, with the help of an example, that the greedy algorithm fails to produce an optimal solution in certain cases. Since Simulated Annealing (SA) is an effective technique to solve computationally hard minimization problems, we implemented SA based schemes to solve both the unweighted and weighted CTE problem. We also implemented three valley descending algorithms each for the weighted and the unweighted CTE problem. Results show that for the unweighted CTE problem the valley descending schemes converge much faster. A possible explanation is—the state space of the unweighted CTE problem is monotonous. However, this is yet to be proved (or disproved). In case of weighted CTE problem the SA based schemes produce better results, whereas the valley descending schemes get stuck at a sub-optimal solution. This is possibly because though the search space of the unweighted CTE problem is monotonous, that of the weighted CTE problem is not. All the schemes were tested with 25 randomly generated problem instances of various sizes.

Indexing terms:

• Complex triangle (CT)
• Rectangular dualization
• Node cover
• Edge-label cover
• Simulated annealing

Additional information

Notes on contributors

Samir Roy

Samir Roy is presently attached to the Department of Computer Science & Engineering of Kalyani Government Engineering College, West Bengal. He obtained his BTech in Computer Science from University College of Science and Technology, Rajabazar, of the University of Calcutta in 1989, ME in Computer Science and Engineering from the Jadavpur University in 1991, and PhD from the University of Kalyani, West Bengal, in 2004. He has twenty five odd articles in various international and national journals, conference proceedings, communications etc. His research interest includes VLSI design and testing, Soft Computing, and Artificial Intelligence.

Ujjwal Maulik

Ujjwal Maulik did his Bachelors in Physics and Computer Science in 1986 and 1989 respectively. Subsequently, he did his Masters and PhD in Computer Science in 1991 and 1997 respectively from Jadavpur University, India. Dr Maulik has visited Center for Adaptive Systems Application, Los Alamos, New Mexico, USA in 1997, University of New South Wales, Sydney, Australia in 1999, University of Texas at Arlington, USA in 2001 and University of Maryland Baltimore County in 2004. He is a faculty member in the Department of Computer Science and Engineering, Jadavpur University, India. Dr Maulik has received the BOYSCAST fellowship of the Department of Science and Technology (DST), Government of India. He has edited a couple, of books and has published more than seventy articles in journals, edited volumes, conference and workshop proceedings. Dr Maulik has served on several program/scientific/technical committees of conferences and symposia, and has also chaired several technical sessions. He is serving as the Tutorial Co-Chair, World Congress on Lateral Computing, 2004, to be held in Bangalore, India. His research interests include Evolutionary Computation and Pattern Recognition, Computer Vision, Parallel and Distributed Systems, VLLI.

Sanghamitra Bandyopadhyay

Sanghamitra Bandyopadhyay did her Bachelors in Physics and Computer Science in 1988 and 1992 respectively. Subsequently, she did her Masters in Computer Science from Indian Institute of Technology (IIT), Kharagpur in 1994 and PhD in Computer Science from Indian Statistical Institute, Calcutta in 1998. Currently she is a faculty-member at Indian Statistical Institute, Kolkata, India. Dr Bandyopadhyay is the first recipient of Dr Shanker Dayal Sharma Gold gold Medal and Institute Silver Medal for being adjudged the best all round post graduate performer in IIT, Kharagpur in 1994. She has worked in Los Alamos National Laboratory, Los Alamos, USA, in 1997, as a graduate research assistant, in the University of New South Wales, Sydney, Australia, in 1999, as a post doctoral fellow, in the Department of Computer Science and Engineering, University of Texas at Arlington, USA, in 2001 as a faculty and researcher, and in the Department of Computer Science and Engineering, University of Maryland-Baltimore County, USA, in 2004 as a visiting research faculty. Dr Bandyopadhyay received the Indian National Science Academy (INSA) and the Indian Science Congress Association (ISCA) Young Scientist Award in 2000, as well as the Indian National Academy of Engineering (INAE) Young Engineers Award in 2002. She has published over seventy articles in international journals, conference and workshop proceedings, edited books and journal special issues and-served on the committees of several conferences. She is serving as the Program Chair of the 1st International Conference on Pattern Recognition and Machine intelligence, 2005, to be held in Kolkata, India, and as the Tutorial Chair, World Congress on Lateral Computing, 2004, to be held in Bangalore, India. She is on the editorial board of the International Journal on Computational Intelligence. Her research interests include Evolutionary and Soft Computation, Pattern Recognition, Data Mining, Bioinformatics, Parallel and Distributed Systems and VLSI.