Selection of Output Elements by Minimum Cost Flow Algorithm
Abstract
During the placement stage of VLSI (Very Large Scale of Integration) physical design phase it is needed to take into account the external connections of the placing elements. So later, it is possible to get better result in routing stage. Thus it is required to map external nets of a circuit to its elements in such a way that the maximum number of nets corresponding to an element is minimal. In this article the problem is solved by reducing it to the problem of finding a minimum cost flow of a given value in a network.
References
N.A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, USA, 1993.
А.В. Петросян, С.Е. Маркосян и Ю.Г. Шукурян, Математические вопросы автоматизации проэктирования ЭВМ, Академия наук Армянкой ССР, 1977.
E.A. Dinits, The method of scaling and transportation problems", Studies in Discrete Mathematics, Moscow, pp. 46-57, 1973.
H.N. Gabow, “Scaling algorithms for network problems", 24th Annual Symposium on Foundations of Computer Science, New York, pp. 248-257, 1983.
H.N. Gabow, “Scaling algorithms for network problems", Journal of Computer and System Science 31, pp. 148-168, 1985.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
