Contents
The paper presents two new strategies for bipartitioning circuits based on fuzzy set theory. For this a new fuzzy net-cut model has been developed treating hypergraphs without splitting multi-pin-nets into two-pin-nets. The first approach is based on a stochastic neural network consisting of continuous Hopfield neurons. The second algorithm is derived from statistical physics modelling the circuit graph as a highly coupled spin system.
Übersicht
Die Arbeit behandelt zwei neue Strategien für die Bipartitionierung elektrischer Schaltungen, die beide auf der Theorie unscharfer Mengen aufbauen. Hierfür haben wir ein Fuzzy-Netzmodell entwickelt, das Hypergraphen ohne eine Aufspaltung der Mehr-Punkt-Netze in Zwei-Punkt-Netze behandeln kann. Der erste Algorithmus basiert auf einem stochastischen Neuronalnetz, das aus kontinuierlichen Hopfield-Neuronen besteht. Der zweite Algorithmus wurde aus der statistischen Physik abgeleitet; der Schaltungsgraph wird als System stark miteinander verkoppelter Spins modelliert.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Garey, M. R.;Johnson, D. S.: Computer and Intractability: A Guide of NP-Completeness. New York, W. H. Freeman, 1979
Engl, W. L.;Mlynski, D. A.: Mengentheorie verallgemeinerter Graphen. Archiv für Elektrotechnik 54 (1972) 278–284
Engl, W. L.;Mlynski, D. A.: Die Schaltungsintegration als graphentheoretisches Syntheseproblem. Archiv für Elektrotechnik 54 (1972) 315–324
Goldstein, A. J.;Schweikert, D. G.: A Proper Model for Testing the Planarity of Electrical Circuits. Bell Syst. Tech. J. 52 (1973) 135–142
Schweikert, D. G.; Kernighan, B. W.: A proper Model for the Partitioning of Electrical Circuits. Proc. 9th Design Automation Workshop (1972) 57–62
Kernighan, B. W.;Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49 (1970) 291–307
Fiduccia, C. M.; Mattheyses, R. M.: A linear-time heuristic for improving network partitions. ACM/IEEE Proc. 19th DAC (1982) 175–181
Hinton, G. E.;Sejnowski, T. J.;Ackley, D. H.: Boltzmann Machines: Constraint Satisfaction Networks that Learn Technical Report CMU-CS-84-119, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1984
Kirkpatrick, S.;Gelatt, C.;Vecchi, M.: Optimization of Simulated Annealing. Science 220 (1983) 671–680
Nahar, S.; Shragowitz, E.: Simulated Annealing and Combinatorial Optimization. ACM/IEEE Proc. 23rd DAC (1986) 293–299
Zadeh, L. A.: Fuzzy Sets and Applications. Selected Papers, New York, Wiley & Sons, 1987
Bezdek, J. C.: Pattern Recognition with Fuzzy Objective Function Algorithms. New York, Plenum Press, 1981
Zimmermann, H. J.: Fuzzy Set Theory and its Applications. Boston, Kluwer Academic Publishers, 1991
Hopfield, J. J.;Tank, D. W.: Neural Computation of Decisions in Optimization Problems. Biological Cybernetics 52 (1985) 141–152
Reif, F.: Fundamentals of Statistical and Thermal Physics. New York, McGraw-Hill, 1965
Geman, S.;Hwang, C.: Diffusions for Global Optimization. SIAM Jounal Control and Optimization 24 (1986) 1031–1043
Haken, H.: Synergetics, an Introduction. Berlin, Springer-Verlag, 1988
Negele, J. W.;Orland, H.: Quantum Many-Particle Systems, New York, Addison-Wesley, 1988
Van den Bout, D. E.;Miller, T. K.: Graph Partitioning Using Annealed Neural Networks. IEEE Transactions on Neural Networks 1 (1990) 192–203
Ball, C. F.; Mlynski, D. A.: Fuzzy Bi- and Multi-Partitioning for Circuits Represented by Hypergraphs, submitted for publication
Author information
Authors and Affiliations
Additional information
This paper is dedicated to Professor Dr. rer. nat. Walter L. Engl, RWTH Aachen, on the occasion of his 70th birthday.
Rights and permissions
About this article
Cite this article
Ball, C.F., Mlynski, D.A. Two new strategies for fuzzy bipartitioning of circuit hypergraphs. Electrical Engineering 79, 135–143 (1996). https://doi.org/10.1007/BF01232923
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01232923