Article

Free access

Multi-way partitioning via spacefilling curves and dynamic programming

Authors:

C. J. Alpert,

A. B. KahngAuthors Info & Claims

DAC '94: Proceedings of the 31st annual Design Automation Conference

Pages 652 - 657

https://doi.org/10.1145/196244.196603

Published: 06 June 1994 Publication History

PDF eReader

References

[1]

C. J. Alpert and A. B. Kahng, "Multi-Way Netlist Partitioning Using Spacefilling Curves," UCLA technical report 9.50016, 1993.

Google Scholar

[2]

C. J. Alpert and A. B. Kahng, "Geometric Embeddings for Faster and Better Multi-way Netlist Partitioning," Proc. A CM/IEEE Design Automation Conf. 1993, pp. 743-748.

Digital Library

Google Scholar

[3]

J. J. Bartholdi and L. K. Platzman, "Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space" Management Sciences Vol. 34, No. 3, March 1988, pp. 291-305.

Digital Library

Google Scholar

[4]

P.K. Chan, M. D. F. Schlag and J. Zien, "Spectral K-Way Ratio Cut Partitioning and Clustering", Proc. Syrup. on Integrated Systems, Seattle, March 1993. (also see J. Zien, "Spectral K-Way Ratio Cut Graph Partitioning", M.S. Thesis, Computer Engineering Dept., UC Santa Cruz, March 1993, for experimental results).

Digital Library

Google Scholar

[5]

C. M, Fiduccia and R. M. Mattheyses, "A Linear Time Heuristic for Improving Network Partitions", Proc. A CM/IEEE Design Automation Conf., June 1982, pp. 175-181.

Digital Library

Google Scholar

[6]

L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD 11(9), Sept. 1992, pp. 1074-1085.

Digital Library

Google Scholar

[7]

K. M. Hall, "An r-dimensional Quadratic Placement Algorithm", Manag. Sci, 17, 1970, pp. 219-229.

Crossref

Google Scholar

[8]

R. M. Karp, "Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane", Mathematics of Operations Research 2(3), 1977, pp. 209- 224.

Digital Library

Google Scholar

[9]

T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley-Teubner, 1990.

Digital Library

Google Scholar

[10]

A. Pothen, H. D. Simon, and K. P. Liou, "Partitioning Sparse Matrices with Eigenvectors of Graphs," SIAM J. Matrix Anal. AppI., vol. 11, pp. 430-452, 1990.

Digital Library

Google Scholar

[11]

L. A. Sanchis, "Multiple-way Network Partitioning", IEEE Trans. on Computers, 38, 1989, pp. 62-81.

Digital Library

Google Scholar

[12]

D. S. Scott, "LASO2 Documentation", technical report, CS Dept., University of Texas at Austin, 1980.

Google Scholar

[13]

H. D. Simon, "Partitioning of Unstructured Problems for Parallel Processing", technical report, NAS Systems Division, NASA Ames Research Center, Feb. 1991.

Google Scholar

[14]

Y. C. Wei and C. K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs", IEEE Trans. on CAD 10(7), July 1991, pp. 911-921.

Digital Library

Google Scholar

[15]

C. W. Yeh, C. K. Cheng and T. T. Lin, "A General Purpose Multiple Way Partitioning Algorithm", Proc. ACM/IEEE Design Automation Conf., June 1991, pp. 421-426.

Digital Library

Google Scholar

Cited By

View all

Kannan RLaurenzano MAhn JMars JTang L(2019)CaliperACM Transactions on Architecture and Code Optimization10.1145/332309016:3(1-25)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323090
Yadav ABerges M(2019)Computer Science Pedagogical Content KnowledgeACM Transactions on Computing Education10.1145/330377019:3(1-24)Online publication date: 21-May-2019
https://dl.acm.org/doi/10.1145/3303770
Denner JCampe SWerner L(2019)Does Computer Game Design and Programming Benefit Children? A Meta-Synthesis of ResearchACM Transactions on Computing Education10.1145/327756519:3(1-35)Online publication date: 16-Jan-2019
https://dl.acm.org/doi/10.1145/3277565
Show More Cited By

Index Terms

Multi-way partitioning via spacefilling curves and dynamic programming

Recommendations

Application of fusion-fission to the multi-way graph partitioning problem
PPAM'07: Proceedings of the 7th international conference on Parallel processing and applied mathematics

This paper presents an application of the Fusion-Fission method to the multi-way graph partitioning problem. The Fusion-Fission method was first designed to solve the normalized cut partitioning problem. Its application to the multi-way graph ...
Rational Pythagorean-hodograph space curves

A method for constructing rational Pythagorean-hodograph (PH) curves in R^3 is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first derivative, defines the orientation of the curve ...
Polynomial curves with projections to PH curves
Abstract
Despite the fact that the orthogonal projection of a spatial Pythagorean hodograph (PH) curve into the plane is not a planar PH curve in general, we can find special cases such that the PH property is preserved when the curve is ...
Graphical abstract
Highlights
- PH curves are characterized via intersection multiplicity of a suitable associated curve with the absolute conic.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '94: Proceedings of the 31st annual Design Automation Conference

June 1994

739 pages

ISBN:0897916530

DOI:10.1145/196244

Chairman:
Michael Lorenzetti
Mentor Graphics Corp., Wilsonville, OR

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC94

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC94: The 31st ACM/IEEE-CAS/EDAC Design Automation Conference

June 6 - 10, 1994

California, San Diego, USA

Acceptance Rates

DAC '94 Paper Acceptance Rate 100 of 260 submissions, 38%;

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

46
Total Citations
View Citations
434
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)11

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kannan RLaurenzano MAhn JMars JTang L(2019)CaliperACM Transactions on Architecture and Code Optimization10.1145/332309016:3(1-25)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323090
Yadav ABerges M(2019)Computer Science Pedagogical Content KnowledgeACM Transactions on Computing Education10.1145/330377019:3(1-24)Online publication date: 21-May-2019
https://dl.acm.org/doi/10.1145/3303770
Denner JCampe SWerner L(2019)Does Computer Game Design and Programming Benefit Children? A Meta-Synthesis of ResearchACM Transactions on Computing Education10.1145/327756519:3(1-35)Online publication date: 16-Jan-2019
https://dl.acm.org/doi/10.1145/3277565
Yang YLuk WZhou HPan DZhou DYan CZeng X(2017)An Effective Layout Decomposition Method for DSA with Multiple Patterning in Contact-Hole GenerationACM Transactions on Design Automation of Electronic Systems10.1145/313184723:1(1-27)Online publication date: 21-Sep-2017
https://dl.acm.org/doi/10.1145/3131847
López CFarzan RLin Y(2017)Behind the Myths of Citizen ParticipationACM Transactions on Internet Technology10.1145/309389218:1(1-28)Online publication date: 4-Nov-2017
https://dl.acm.org/doi/10.1145/3093892
Shahzad MLiu A(2014)Noise can helpACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198842:1(207-219)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591988
Gabielkov MRao ALegout A(2014)Studying social networks at scaleACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198542:1(277-288)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591985
Meyfroyt TBorst SBoxma ODenteneer D(2014)Data dissemination performance in large-scale sensor networksACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198142:1(395-406)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591981
Shi WZhang LWu CLi ZLau F(2014)An online auction framework for dynamic resource provisioning in cloud computingACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198042:1(71-83)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591980
Chan TKahng A(2012)Improved path clustering for adaptive path-delay testingThirteenth International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2012.6187468(13-20)Online publication date: Mar-2012
https://doi.org/10.1109/ISQED.2012.6187468
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Application of fusion-fission to the multi-way graph partitioning problem

Rational Pythagorean-hodograph space curves

Polynomial curves with projections to PH curves