A Survey: Hypergraph Partitioning Techniques

Graphs are formed by vertices and edges where any two objects joined using edge that represents some relationships between these objects. Hyper graph is a abstraction of graph in which edges are non-empty subset of vertex set. It do not have edges between pair of vertices that is hypergraph has edges that connect set of two or more vertices.Hypergraph are more suitable to represent complex relational objects in many real-world problems. Partitioning decomposes a set of interrelated objects into a set of subsets or parts to optimize a specified objective. In general, it is required that any two objects within the same part should be strongly related in some criteria , whereas the converse should hold for any two objects found in different parts. Both graphs & hypergraphs may be partitioned to optimize some objective. The hypergraph partitioning problem has use in many scientific computing and provides a more accurate inter-processor communication model for distributed systems than the similar graph problem. Here we are discussing hypergraph partitioning methods Iterative algorithm, spectral partitioning and multi-level partitioning in detail. Advantages and disadvantages are also listed.