Computational study of graph partitioning

被引:0
|
作者
Falkner, Julie [1 ]
Rendl, Franz [1 ]
Wolkowicz, Henry [1 ]
机构
[1] Massey Univ, Palmerston North, New Zealand
来源
Mathematical Programming, Series B | 1994年 / 66卷 / 02期
关键词
Computational complexity - Eigenvalues and eigenfunctions - Heuristic methods - Integrated circuit layout - Mathematical programming - Optimization - VLSI circuits;
D O I
暂无
中图分类号
学科分类号
摘要
Let G = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node set N into k disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.
引用
收藏
页码:211 / 239
相关论文
共 50 条
  • [1] A COMPUTATIONAL STUDY OF GRAPH PARTITIONING
    FALKNER, J
    RENDL, F
    WOLKOWICZ, H
    MATHEMATICAL PROGRAMMING, 1994, 66 (02) : 211 - 239
  • [2] The node capacitated graph partitioning problem: A computational study
    C. E. Ferreira
    A. Martin
    C. C. de Souza
    R. Weismantel
    L. A. Wolsey
    Mathematical Programming, 1998, 81 : 229 - 256
  • [3] The node capacitated graph partitioning problem: A computational study
    Ferreira, CE
    Martin, A
    de Souza, C
    Weismantel, R
    Wolsey, LA
    MATHEMATICAL PROGRAMMING, 1998, 81 (02) : 229 - 256
  • [4] The effect of graph partitioning techniques on parallel Block FSAI preconditioning: a computational study
    Carlo Janna
    Nicola Castelletto
    Massimiliano Ferronato
    Numerical Algorithms, 2015, 68 : 813 - 836
  • [5] The effect of graph partitioning techniques on parallel Block FSAI preconditioning: a computational study
    Janna, Carlo
    Castelletto, Nicola
    Ferronato, Massimiliano
    NUMERICAL ALGORITHMS, 2015, 68 (04) : 813 - 836
  • [6] Graph Database Partitioning: A Study
    Ben Ammar, Ali
    2016 7TH INTERNATIONAL CONFERENCE ON INFORMATION, INTELLIGENCE, SYSTEMS & APPLICATIONS (IISA), 2016,
  • [7] Computational Comparison of Major Proposed Methods for Graph Partitioning Problem
    Rais, Helmi Md
    Abed, Saad Adnan
    Watada, Junzo
    JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS, 2019, 23 (01) : 5 - 17
  • [8] Streaming Graph Partitioning: An Experimental Study
    Abbas, Zainab
    Kalavri, Vasiliki
    Carbone, Paris
    Vlassov, Vladimir
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2018, 11 (11): : 1590 - 1603
  • [9] A study of graph partitioning schemes for parallel graph community detection
    Zeng, Jianping
    Yu, Hongfeng
    PARALLEL COMPUTING, 2016, 58 : 131 - 139
  • [10] A computational-graph partitioning method for training memory-constrained DNNs
    Qararyah, Fareed
    Wahib, Mohamed
    Dikbayir, Doga
    Belviranli, Mehmet Esat
    Unat, Didem
    PARALLEL COMPUTING, 2021, 104