research-article

Generalization of Min-Cut Partitioning to Tree Structures and its Applications

Author:

Gopalakrishnan VijayanAuthors Info & Claims

IEEE Transactions on Computers, Volume 40, Issue 3

Pages 307 - 314

https://doi.org/10.1109/12.76407

Published: 01 March 1991 Publication History

Publisher Site

Abstract

A generalization of the min-cut partitioning problem, called min-cost tree partitioning, is introduced. In the generalized problem. the nodes of a hypergraph G are to be mapped onto the vertices of a tree structure T, and the cost function to be minimized is the cost of routing the hyperedges of G on the edges of T. The standard min-cut problem is the simple case in which the tree T is a single edge connecting two vertices. Several VLSI design applications for this problem are discussed. An iterative improvement heuristic for this problem in which nodes of the hypergraph are moved between the vertices of the tree is described. The running time of a single pass of the heuristic for the unweighted version of the problem is Q(P*D*t/sup 3/), where P is the total number of pins in the hypergraph G, D is the maximum number of nodes in a hyperedge of G, and t is the number of vertices in the tree T. Several test results are discussed.

References

[1]

{1} A. V. Aho, J. E. Hopcroft, and J. E. Ullman, The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974.

Digital Library

Google Scholar

[2]

{2} I. Bhandari, M. Hirsch, and D. Siewiorek, "The min-cut shuffle: Toward a solution for the global effect problem of min-cut placement," in Proc. 25th ACM/IEEE Design Automat. Conf., Anaheim, CA, June 1988.

Digital Library

Google Scholar

[3]

{3} A. E. Dunlop, "A procedure for placement of standard cell VLSI circuits," IEEE Trans. Comput.-Aided Design Integrated Circuits Syst., vol. CAD-4, 1985.

Google Scholar

[4]

{4} C. M. Fiduccia and R. M. Mattheyses, "A linear-time heuristic for improving network partitions," in Proc. 19th ACM/IEEE Design Automat. Conf., Las Vegas, NV, June 1982.

Digital Library

Google Scholar

[5]

{5} M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

Digital Library

Google Scholar

[6]

{6} B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell Syst. Tech. J., vol. 49, Feb. 1970.

Crossref

Google Scholar

[7]

{7} B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI networks," IEEE Trans. Comput., vol. C-33, no. 5, May 1984.

Google Scholar

[8]

{8} D. Lapotin and S. W. Director, "Mason: A global floorplanning approach for VLSI design," IEEE Trans. Comput.-Aided Design Integrated Circuits Syst. vol. CAD-5, 1986.

Google Scholar

[9]

{9} L. A. Sanchis, "Multiple-way network partitioning," IEEE Trans. Comput., vol. 38, no. 1, pp. 62-81, Jan. 1989.

Digital Library

Google Scholar

Cited By

View all

Cho S(2007)Geometrical k-cut problem and an optimal solution for hypercubesProceedings of the 12th WSEAS International Conference on Applied Mathematics10.5555/1376368.1376405(217-221)Online publication date: 29-Dec-2007
https://dl.acm.org/doi/10.5555/1376368.1376405
Kahng ASarrafzadeh M(1998)Futures for partitioning in physical design (tutorial)Proceedings of the 1998 international symposium on Physical design10.1145/274535.274563(190-193)Online publication date: 1-Apr-1998
https://dl.acm.org/doi/10.1145/274535.274563
Cho JRaje SSarrafzadeh M(1998)Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering for VLSI ApplicationsIEEE Transactions on Computers10.1109/12.73644047:11(1253-1266)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1109/12.736440
Show More Cited By

Index Terms

Generalization of Min-Cut Partitioning to Tree Structures and its Applications
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
  2. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Wirelength minimization for min-cut placements via placement feedback

The advent of strong multilevel partitioners has made top-down min-cut placers a favored choice for modern placer implementations. Terminal propagation is an important step in min-cut placers because it translates partitioning results into global-...
Equality of domination and transversal numbers in hypergraphs

A subset S of the vertex set of a hypergraph H is called a dominating set of H if for every vertex v not in S there exists u@__ __S such that u and v are contained in an edge in H. The minimum cardinality of a dominating set in H is called the ...
Covering Non-uniform Hypergraphs

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 40, Issue 3

March 1991

133 pages

ISSN:0018-9340

Editor:
Earl Swartzlander
Univ. of Texas at Austin, Austin

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 March 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cho S(2007)Geometrical k-cut problem and an optimal solution for hypercubesProceedings of the 12th WSEAS International Conference on Applied Mathematics10.5555/1376368.1376405(217-221)Online publication date: 29-Dec-2007
https://dl.acm.org/doi/10.5555/1376368.1376405
Kahng ASarrafzadeh M(1998)Futures for partitioning in physical design (tutorial)Proceedings of the 1998 international symposium on Physical design10.1145/274535.274563(190-193)Online publication date: 1-Apr-1998
https://dl.acm.org/doi/10.1145/274535.274563
Cho JRaje SSarrafzadeh M(1998)Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering for VLSI ApplicationsIEEE Transactions on Computers10.1109/12.73644047:11(1253-1266)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1109/12.736440
Kuo MCheng CYoffa EDe Micheli GRabaey J(1997)A network flow approach for hierarchical tree partitioningProceedings of the 34th annual Design Automation Conference10.1145/266021.266269(512-517)Online publication date: 13-Jun-1997
https://dl.acm.org/doi/10.1145/266021.266269
Kuo MLiu LCheng CPennino TYoffa E(1996)Network partitioning into tree hierarchiesProceedings of the 33rd annual Design Automation Conference10.1145/240518.240609(477-482)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/240518.240609
Tragoudas S(1996)Min-Cut Partitioning on Underlying Tree and Graph StructuresIEEE Transactions on Computers10.1109/12.49410445:4(470-474)Online publication date: 1-Apr-1996
https://dl.acm.org/doi/10.1109/12.494104

Abstract

References

Cited By

Index Terms

Recommendations

Wirelength minimization for min-cut placements via placement feedback

Equality of domination and transversal numbers in hypergraphs

Covering Non-uniform Hypergraphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations