CFP last date
20 June 2024
Reseach Article

Hypergraph Partitioning Algorithm

Published on March 2017 by Chandani Santosh Jain, S. M. Kamalapur
Emerging Trends in Computing
Foundation of Computer Science USA
ETC2016 - Number 2
March 2017
Authors: Chandani Santosh Jain, S. M. Kamalapur

Chandani Santosh Jain, S. M. Kamalapur . Hypergraph Partitioning Algorithm. Emerging Trends in Computing. ETC2016, 2 (March 2017), 11-14.

author = { Chandani Santosh Jain, S. M. Kamalapur },
title = { Hypergraph Partitioning Algorithm },
journal = { Emerging Trends in Computing },
issue_date = { March 2017 },
volume = { ETC2016 },
number = { 2 },
month = { March },
year = { 2017 },
issn = 0975-8887,
pages = { 11-14 },
numpages = 4,
url = { /proceedings/etc2016/number2/27308-6261/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Proceeding Article
%1 Emerging Trends in Computing
%A Chandani Santosh Jain
%A S. M. Kamalapur
%T Hypergraph Partitioning Algorithm
%J Emerging Trends in Computing
%@ 0975-8887
%V ETC2016
%N 2
%P 11-14
%D 2017
%I International Journal of Computer Applications

Hypergraph is an abstraction of graph in which edges are non-empty subset of vertex set. 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. There is need to make the partitions of the hypergraph to analyze the whole hypergraph. Multilevel partitioning techniques are used to obtain subgraph. Sometimes they are inadequate to follow global objective function. Here hypergraph partitioning is making partitions of vertex set into the subset of vertices which are distributed smoothly to form subgraphs and having minimum intersections between this subgraphs. The hypergraph partitioning problem is used in many scientific computing, social network analysis than the similar graph problem.

  1. D. Zhou, J. Huang, and B. Scholkopf, "Learning with hypergraphs: Clustering, classification, and embedding," in Proc. Adv. Neural Inf. Process. Syst. , 2006, pp. 1601–1608.
  2. S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo, "Higher-order correlation clustering for image segmentation," inProc. Adv. Neural Inf. Process. Syst. , 2011, pp. 1530–1538.
  3. R. Zass and A. Shashua, "Probabilistic graph and hypergraph matching," inProc. IEEE Conf. Comput. Vis. Pattern Recog. , 2008, pp. 1–8.
  4. B. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs,"Bell Syst. Tech. J. , vol. 49, pp. 291– 307, 1970.
  5. C. Fiduccia and R. Mattheyses, "A linear-time heuristic for improving network partitions," in Proc. 19th Conf. Des. Autom. , 1982, pp. 175–181.
  6. J. Rodr?guez, "Laplacian eigenvalues and partition problems in hypergraphs,"Appl. Math. Letters, vol. 22, no. 6, pp. 916–921, 2009
  7. M. Newman, "Modularity and community structure in networks,"Proc. Nat. Acad. Sci. , vol. 103, no. 23, pp. 8577– 8582, 2006.
  8. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel hypergraph partitioning: Application in vlsi domain," inProc. 34th Annu. Des. Autom. Conf. , 1997, pp. 526–529.
  9. G. Karypis and V. Kumar, "hmetis: A hypergraph partitioning package, version 1. 5. 3," 1998.
  10. F. Lotfar and M. Johnson," A Multi Level Hypergraph Partitioning Algorithm using Rough Set Clustering", School of Engineering and Computing Sciences, Durham University, United Kingdom, 2015
  11. G. Karypis and V. Kumar," Multilevel k-way Hypergraph Partitioning", Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, Minneapolis,2000, Vol. 11, No. 3, pp. 285-300
  12. H. Liu, L. J. Latecki, S. Yan ," Dense Subgraph Partition of Positive Hypergraphs", IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 37, No. 3, March 2015
  13. C. Jain , S. Kamalapur ,"Hypergraph Partitioning Algorithm", cPGCON 2016
Index Terms

Computer Science
Information Sciences


Hypergraph Hypergraph Partitioning Dense Subgraph