Hypergraph Partitioning

Umit V. Catalyurek (1) , Bora Uçar (2) , Cevdet Aykanat (3)

1 Department of Biomedical Informatics [Columbus]
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 Bilkent-CS - Department of Computer Engineering

Hypergraphs are generalization of graphs where each edge (hyperedge) can connect more than two vertices. In simple terms, the hypergraph partitioning problem can be defined as the task of dividing the vertices of hypergraph into two or more roughly equal sized parts such that a cost function on the hyperedges connecting vertices in different parts is minimized.

Domaines: Informatique [cs]; Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Umit V. Catalyurek, Bora Uçar, Cevdet Aykanat. Hypergraph Partitioning. David A. Padua. Encyclopedia of Parallel Computing, Springer, pp.871--881, 2011. ⟨hal-00786552⟩