A fast hypergraph min-cut algorithm for circuit partitioning

DOI10.1016/S0167-9260(00)00008-0MaRDI QIDQ2734604zbMATH OpenFDO

Authors W.-K. Mak, D. F. Wong

Publication date 20 August 2001

Published in Integration. The VLSI Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-9260(00)00008-0

zbMATH Keywords

circuit partitioningflow-based algorithmhypergraphmin-cut partitioningminimum cutnon-flow-based algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Review text

Circuit partitioning is one of the central problems in VLSI system design. The primary objective of circuit partitioning is to minimize the number of interconnections between different components of the partitioned circuit. So the circuit partitioning problem is closely related to the minimum cut problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported [\textit{H. Nagamochi} and \textit{T. Ibaraki}, SIAM J. Discrete Math. 5, No. 1, 54-66 (1992; Zbl 0754.05062)]. However, it is known that a circuit netlist cannot be accurately modeled by a graph, but only by a hypergraph. In this paper, we present the fastest algorithm known today for computing a minimum cut in a hypergraph which is a non-trivial extension of the result in \textit{M. Stoer} and \textit{F. Wagner} [J. ACM 44, No. 4, 585-591 (1997; Zbl 0891.68071)]. Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding very-high-quality solutions for the circuit partitioning problem. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow-based algorithm.

Recommendations

• Min-cut partitioning on underlying tree and graph structures
• scientific article; zbMATH DE number 139787
• Computing minimum multiway cuts in hypergraphs
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• A Gomory-Hu cut tree representation of a netlist partitioning problem

Cited in

(24)

• A note on hypergraph decomposition based on extended minimal sets
• Modeling hypergraphs by graphs with the same mincut properties
• Computing minimum multiway cuts in hypergraphs
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Hypergraph \(k\)-cut in randomized polynomial time
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Constrained Min-Cut Replication for K-Way Hypergraph Partitioning
• Recent directions in netlist partitioning: a survey
• A Gomory-Hu cut tree representation of a netlist partitioning problem
• scientific article; zbMATH DE number 3912287 (Why is no real title available?)
• scientific article; zbMATH DE number 139787 (Why is no real title available?)
• Min-cut partitioning on underlying tree and graph structures
• scientific article; zbMATH DE number 1982182 (Why is no real title available?)
• Minimum cuts and sparsification in hypergraphs
• Computing the map of geometric minimal cuts
• Design and implementation of move-based heuristics for VLSI hypergraph partitioning
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• A direct k-way hypergraph partitioning algorithm for optimizing the Steiner tree metric
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Minimum s-t hypercut in (s, t)-planar hypergraphs
• Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
• Finding minimum 3-way cuts in hypergraphs
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• Mathematical methods for physical layout of printed circuit boards: an overview

This page was built for publication: A fast hypergraph min-cut algorithm for circuit partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2734604)