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)

zbMATH Keywords

hypergraphsVLSI layoutedge-weighted hypergraphedge-weighted graphcut propertiescut-modelgraph partitioning algorithms

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65) 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

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

Cited in

(11)

• Weighted fundamental group
• Relaxation-based coarsening for multilevel hypergraph partitioning
• Spectral partitioning with multiple eigenvectors
• The Fiedler vector of a Laplacian tensor for hypergraph partitioning
• A semidefinite programming approach to the hypergraph minimum bisection problem
• Network Flow-Based Refinement 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
• Worst-case ratios of networks in the rectilinear plane
• An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
• Hypergraph Cuts with General Splitting Functions

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)