错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimum \( s-t \) hypercut in (st)-planar hypergraphs

  • Abolfazl Hassanpour,
  • Massoud Aman,
  • Alireza Ebrahimi

摘要

Planar hypergraphs are widely used in several applications, including VLSI design, metro maps, information visualisation, and databases. The minimum \( s-t \) s - t hypercut problem in a weighted hypergraph is to find a partition of the vertices into two nonempty sets, S and \( \overline{S} \) S ¯ , with \(s\in S\) s S and \(t\in \overline{S}\) 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 \) s - t hypercut problem in (st)-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.