Volume 9 Number 8 (Aug. 2014)
Home > Archive > 2014 > Volume 9 Number 8 (Aug. 2014) >
JCP 2014 Vol.9(8): 1886-1896 ISSN: 1796-203X
doi: 10.4304/jcp.9.8.1886-1896

A Vertex Separator-based Algorithm for Hypergraph Bipartitioning

Enli Zhang, Lin Gao
School of Computer Science and Technology, Xidian University, Xi’an, China

Abstract—Hypergraph partitioning is critical for dividing and conquering intractable problems in many complex systems, which is an NP-hard problem. In the paper, a novel hypergraph bipartitioning algorithm is proposed, which partitions the hypergraph by separating the intersection graph. The new approach completely eliminates the adverse effects of hyperedges with large cardinality on the performance of the vertex-oriented refinement algorithms, and enhances the hill-climbing ability of the move-based refinement algorithms. Our approach also simplifies the vertex designation. Experiments on the industrial testing benchmark datasets indicate that our approach achieves an average of 7% improvement in performance over FM family partitioning algorithms.

Index Terms—Hypergraph Bipartitioning, Multileve Algorithm, Vertex Separator

[PDF]

Cite: Enli Zhang, Lin Gao, "A Vertex Separator-based Algorithm for Hypergraph Bipartitioning," Journal of Computers vol. 9, no. 8, pp. 1886-1896, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>