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)

zbMATH Keywords

hypergraphminimum cutcircuit partitioningflow-based algorithmmin-cut partitioningnon-flow-based algorithm

Mathematics Subject Classification ID

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

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

(23)

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

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)