1. Minimum s-t hypercut in (s, t)-planar hypergraphs.
- Author
-
Hassanpour, Abolfazl, Aman, Massoud, and Ebrahimi, Alireza
- Abstract
Planar hypergraphs are widely used in several applications, including VLSI design, metro maps, information visualisation, and databases. The minimum s - t hypercut problem in a weighted hypergraph is to find a partition of the vertices into two nonempty sets, S and S ¯ , with s ∈ S and t ∈ S ¯ that minimizes the total weight of hyperedges that have at least two endpoints in two different sets. In the present study, we propose an approach that effectively solves the minimum s - t hypercut problem in (s, t)-planar hypergraphs. The method proposed demonstrates polynomial time complexity, providing a significant advancement in solving this problem. The modelling example shows that the proposed strategy is effective at obtaining balanced bipartitions in VLSI circuits. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF