Modeling hypergraphs by graphs with the same mincut properties

DOI10.1016/0020-0190(93)90115-PMaRDI QIDQ1209979zbMATH OpenFDO

Authors S. Singh

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90115-P

zbMATH Keywords

cut propertiescut-modeledge-weighted graphedge-weighted hypergraphgraph partitioning algorithmshypergraphsVLSI layout

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• A fast hypergraph min-cut algorithm for circuit partitioning
• Minimum cut and minimum k-cut in hypergraphs via branching contractions
• Finding Minimum 3-Way Cuts in Hypergraphs
• Computing minimum cuts in hypergraphs
• Finding minimum 3-way cuts in hypergraphs

Cites work

• A framework for solving VLSI graph layout problems
• A Gomory-Hu cut tree representation of a netlist partitioning problem
• An Algorithm for Partitioning the Nodes of a Graph
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)

Cited in

(11)

• Spectral partitioning with multiple eigenvectors
• Weighted fundamental group
• Worst-case ratios of networks in the rectilinear plane
• A semidefinite programming approach to the hypergraph minimum bisection problem
• The Fiedler vector of a Laplacian tensor for hypergraph partitioning
• An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
• Hypergraph Cuts with General Splitting Functions
• Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
• Relaxation-based coarsening for multilevel hypergraph partitioning
• Comparing hypergraphs by areas of hyperedges drawn on a convex polygon
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

This page was built for publication: Modeling hypergraphs by graphs with the same mincut properties

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