ENISLE: A Clustering Algorithm for Nearly Maximal and Minimal Connection on Hypergraph

Kou-Hsing  Cheng; Shun-Wen  Cheng

doi:10.6180/jase.2005.8.2.08

ENISLE: A Clustering Algorithm for Nearly Maximal and Minimal Connection on Hypergraph

Kou-Hsing Cheng¹ and Shun-Wen Cheng This email address is being protected from spambots. You need JavaScript enabled to view it.²

¹Department of Electrical Engineering, National Central University Taoyuan, Taiwan 320, R.O.C.
²Department of Electrical Engineering, Tamkang University Tamsui, Taiwan 251, R.O.C.

Received: January 6, 2005
Accepted: March 11, 2005
Publication Date: June 1, 2005

Download Citation: ||https://doi.org/10.6180/jase.2005.8.2.08

ABSTRACT

This work presents two approaches with a high probability of obtaining maximal and minimal connection in an electrical network. The first method, referred to herein as Edge-Node Interleaved Sort for Leaching and Envelop (ENISLE) algorithm, uses both node information and edge information and works effectively on a common network. The second method, referred to herein as Interleaved Cutting-ENISLE (IC-ENISLE) algorithm, uses node and edge information as well as the max-min dual property. This method works better than ENISLE in an electrical circuit. This study also finds the relationship between minimal connection and the initial node-edge pairs distributed condition/entropy on hypergraph circuit. Under a nearly max-connection reservation, a circuit with a high initial potential/entropy implies a high probability of aiming the minimal connection. From our approach, the work indicates that the minimum connection plane characteristics significantly affect the connection problems. Our results further demonstrate that, with respect to the sequential circuit or other time-sensitive circuits as an indivisible element, record the level is even or odd, and/or record the level number of every node or edge, are highly effective for modern circuit network connection.

Keywords: ENISLE, Minimal-connection, Quasi-random, Clustering Effect, Radix Sort, Hypergraph, VLSI Circuit

REFERENCES

[1] Garbers, J., Promel, H. J. and Steger, A., “Finding Clusters in VLSI circuits,” Proc. IEEE/ACM Int. Conf. Computer-Aided Design, ICCAD, Vol. 90, pp. 520–523 (1990).
[2] Sherwani, N. A., Algorithms for VLSI Physical Design Automation. 3rd Ed., Kluwer, Boston, MA, U.S.A. (1999).
[3] Sechen, C., VLSI Placement & Global Routing Using Simulated Annealing. Kluwer, Amsterdam, Netherlands (1988).
[4] Akers, S. B., “Clustering Techniques for VLSI,” Proc. IEEE Int. Symp. on Circuits and Systems, ISCAS Vol. 82, pp. 472–476 (1982).
[5] Cheng, S.-W. and Cheng, K.-H., “ENISLE: An Intuitive Heuristic Nearly Optimal Solution for Mincut and Ratio Mincut Partitioning,” Proc. IEEE Int. Symp. on Circuits and Systems, ISCAS 2001, Vol. 5, pp. 167–170 (2001).
[6] Knuth, D. E., Sorting and Searching, Addison-Wesley, Redwood, CA, U.S.A. (1973).
[7] Saab, Y. G., “A Fast and Robust Network Bisection Algorithm,” IEEE Trans. Computers, pp. 903–913 (1995).
[8] Cheng, K.-H. and Cheng, S.-W., “A Study on the Relationship Between Initial Node-Edge Pairs Entropy and Mincut Circuit Partitioning,” Proc. IEEE Int. Conf. on Electronics, Circuits and Systems, ICECS 2001, pp. 889–893 (2001).
[9] Cheng, K.-H. and Cheng, S.-W., Method of Mincut and Ratio Mincut (on Electrical Circuit). Patent No. 182649, Taiwan, R.O.C., Nov. 24 (2003).
[10] Garey, M. R. and Johnson, D. S., Computers and Intractability, Freeman, San Francisco, CA, U.S.A. pp. 209–210 (1980).