Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems

DOI10.1007/3-540-53832-1_39MaRDI QIDQ4028112zbMATH OpenFDO

Authors S. Tragoudas, Fillia Makedon

Publication date 28 March 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-53832-1_39

zbMATH Keywords

approximationcircuit partitioning problemshypergraphminimum net expansionmulticommodity flow problemoptimal solutionpolynomial time

Mathematics Subject Classification ID

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25) Circuits, networks (94C99)

Recommendations

• A fast hypergraph min-cut algorithm for circuit partitioning
• scientific article; zbMATH DE number 3891429
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• Multicommodity flow approximation used for exact graph partitioning
• Min-cut partitioning on underlying tree and graph structures

Cited in

(2)

• A fast hypergraph min-cut algorithm for circuit partitioning
• A Gomory-Hu cut tree representation of a netlist partitioning problem

This page was built for publication: Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems

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