Article

Free access

A linear-time heuristic for improving network partitions

Authors:

C. M. Fiduccia,

R. M. MattheysesAuthors Info & Claims

DAC '82: Proceedings of the 19th Design Automation Conference

Pages 175 - 181

Published: 01 January 1982 Publication History

PDF eReader

Abstract

An iterative mincut heuristic for partitioning networks is presented whose worst case computation time, per pass, grows linearly with the size of the network. In practice, only a very small number of passes are typically needed, leading to a fast approximation algorithm for mincut partitioning. To deal with cells of various sizes, the algorithm progresses by moving one cell at a time between the blocks of the partition while maintaining a desired balance based on the size of the blocks rather than the number of cells per block. Efficient data structures are used to avoid unnecessary searching for the best cell to move and to minimize unnecessary updating of cells affected by each move.

References

[1]

M.A. Breuer, "Min-Cut Placement," J. of Design and Fault- Tolerant Computing, Vol.1, number 4, Oct. 1977, pp. 343-362.

Google Scholar

[2]

M.A. Breuer, "A Class of Min-Cut Placement Algorithms," Proc. 14th Design Automation Conference, New Orleans, 1977, pp. 284-290.

Digital Library

Google Scholar

[3]

B.W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, Vol. 49, Feb. 1970, pp. 291-307.

Google Scholar

[4]

D.G. Schweikert and B.W. Kernighan, "A Proper Model for the Partitioning of Electrical Circuits," Proc. 9th Design Automation Workshop, Dallas, June 1979, pp. 57-62.

Digital Library

Google Scholar

[5]

H. Shiraishi and F. Hirose, "Efficient Placement and Routing for Masterslice LSI," Proc. 17th Design Automation Conference, Minneapolis, June 1980, pp. 458-464.

Digital Library

Google Scholar

Cited By

View all

Emami MKashani SKamahori KPourghannad MRaj RLarus JAamodt TSwift MJerger N(2023)Manticore: Hardware-Accelerated RTL Simulation with Static Bulk-Synchronous ParallelismProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624750(219-237)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3623278.3624750
Çatalyürek ÜDevine KFaraj MGottesbüren LHeuer TMeyerhenke HSanders PSchlag SSchulz CSeemaier DWagner D(2023)More Recent Advances in (Hyper)Graph PartitioningACM Computing Surveys10.1145/357180855:12(1-38)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3571808
Lee CLi YChen YWang CTakahashi A(2023)Approximate Logic Synthesis by Genetic Algorithm with an Error Rate GuaranteeProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567890(146-151)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567890
Show More Cited By

Index Terms

A linear-time heuristic for improving network partitions
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

Two efficient constructive heuristics for the Fm|block|Ci are proposed.We show that the insertion phase of heuristic NEH can worsen the solution.The structure of each constructive method is used in a GRASP combined with VNS.The computational evaluation ...
Heterogeneous Multi-commodity Network Flows over Time
Computer Science – Theory and Applications
Abstract
In the 1950’s, Ford and Fulkerson introduced dynamic flows by incorporating the notion of time into the network flow model (Oper. Res., 1958). In this paper, motivated by real-world applications including route planning and evacuations, we extend ...
A Multilevel Memetic Approach for Improving Graph k-Partitions

Graph partitioning is one of the most studied NP-complete problems. Given a graph $G=(V, E)$ , the task is to partition the vertex set $V$ into $k$ disjoint subsets of about the same size, such that the number of edges with endpoints in different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '82: Proceedings of the 19th Design Automation Conference

January 1982

919 pages

ISBN:0897910206

Publisher

IEEE Press

Publication History

Published: 01 January 1982

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

511
Total Citations
View Citations
3,322
Total Downloads

Downloads (Last 12 months)170
Downloads (Last 6 weeks)32

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Emami MKashani SKamahori KPourghannad MRaj RLarus JAamodt TSwift MJerger N(2023)Manticore: Hardware-Accelerated RTL Simulation with Static Bulk-Synchronous ParallelismProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624750(219-237)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3623278.3624750
Çatalyürek ÜDevine KFaraj MGottesbüren LHeuer TMeyerhenke HSanders PSchlag SSchulz CSeemaier DWagner D(2023)More Recent Advances in (Hyper)Graph PartitioningACM Computing Surveys10.1145/357180855:12(1-38)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3571808
Lee CLi YChen YWang CTakahashi A(2023)Approximate Logic Synthesis by Genetic Algorithm with an Error Rate GuaranteeProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567890(146-151)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567890
Biswas SChen FChen ZLu CRamakrishnan N(2023)Memetic Algorithms for Spatial Partitioning ProblemsACM Transactions on Spatial Algorithms and Systems10.1145/35447799:1(1-31)Online publication date: 12-Jan-2023
https://dl.acm.org/doi/10.1145/3544779
Schlag SHeuer TGottesbüren LAkhremtsev YSchulz CSanders P(2023)High-Quality Hypergraph PartitioningACM Journal of Experimental Algorithmics10.1145/352909027(1-39)Online publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1145/3529090
Yang XZhou DLiu SYe JWang XKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Deep model reassemblyProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602136(25739-25753)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602136
Li LOrailoglu ABolchini CO'Connor IVerbauwhede IWille R(2022)JANUS-HDProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540155(1323-1328)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540155
Liu YJu ZLi ZDong MZhou HWang JYang FZeng XShang L(2022)GraphPlanner: Floorplanning with Graph Neural NetworkACM Transactions on Design Automation of Electronic Systems10.1145/355580428:2(1-24)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1145/3555804
Khasawneh MMadden PBehjat LYang S(2022)What's So Hard About (Mixed-Size) Placement?Proceedings of the 2022 International Symposium on Physical Design10.1145/3505170.3511035(57-64)Online publication date: 13-Apr-2022
https://dl.acm.org/doi/10.1145/3505170.3511035
Skandylas CKhakpour NAndersson J(2021)AT-DIFC+: Toward Adaptive and Trust-Aware Decentralized Information Flow ControlACM Transactions on Autonomous and Adaptive Systems10.1145/348729215:4(1-35)Online publication date: 20-Dec-2021
https://dl.acm.org/doi/10.1145/3487292
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

Heterogeneous Multi-commodity Network Flows over Time

A Multilevel Memetic Approach for Improving Graph k-Partitions

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations