Approximation techniques for hypergraph partitioning problems

DOI10.1016/0166-218X(93)E0166-VMaRDI QIDQ1891922zbMATH OpenFDO

Authors Scott W. Hadley

Publication date 26 October 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)E0166-V

zbMATH Keywords

approximationshypergraphhypergraph partitioningnode partitioning algorithmsweighted graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Review text

The paper discusses techniques for approximating a hypergraph by a weighted graph. This has potential applications in node partitioning algorithms. The approximations are compared with other known approximations and according to the author yield promising results.

Recommendations

• scientific article; zbMATH DE number 2075198
• Approximation algorithms in combinatorial scientific computing
• Finding a minimal spanning hypertree of a weighted hypergraph
• scientific article; zbMATH DE number 4187850
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle

Cites work

• A Gomory-Hu cut tree representation of a netlist partitioning problem
• A method for finding minimal bottle-neck cells for grouping part-machine families†
• A parallel graph partitioning algorithm for a message-passing multiprocessor
• A projection technique for partitioning the nodes of a graph
• An Algorithm for Partitioning the Nodes of a Graph
• Design of generalized double rank and multiple rank sequential circuits
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3902554 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3316542 (Why is no real title available?)
• Partitioning Sparse Matrices with Eigenvectors of Graphs

Cited in

(10)

• Finding a minimal spanning hypertree of a weighted hypergraph
• Approximation algorithms for maximization problems arising in graph partitioning
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• scientific article; zbMATH DE number 4076980 (Why is no real title available?)
• Finding part-machine families using graph partitioning techniques
• scientific article; zbMATH DE number 2079358 (Why is no real title available?)
• Hypergraph Cuts with General Splitting Functions
• scientific article; zbMATH DE number 4187850 (Why is no real title available?)
• Partitioning problems in dense hypergraphs
• Minimum s-t hypercut in (s, t)-planar hypergraphs

This page was built for publication: Approximation techniques for hypergraph partitioning problems

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