More Recent Advances in (Hyper)Graph Partitioning

被引：29

作者：

Catalyurek, Umit ^{[1
]}

Devine, Karen ^{[2
]}

Faraj, Marcelo ^{[3
]}

Gottesbueren, Lars ^{[4
]}

Heuer, Tobias ^{[4
]}

Meyerhenke, Henning ^{[5
]}

Sanders, Peter ^{[4
]}

Schlag, Sebastian ^{[6
]}

Schulz, Christian ^{[3
]}

Seemaier, Daniel ^{[4
]}

Wagner, Dorothea ^{[4
]}

机构：

[1] Georgia Inst Technol, North Ave, Atlanta, GA 30332 USA

[2] Sandia Natl Labs, POB 5800, Albuquerque, NM 87185 USA

[3] Heidelberg Univ, Neuenheimer Feld 205, D-69120 Heidelberg, Baden Wurttembe, Germany

[4] Karlsruhe Inst Technol, Fasanengarten 5, D-76131 Karlsruhe, Germany

[5] Humboldt Univ, Unter den Linden 6, D-10099 Berlin, Germany

[6] Apple Inc, Cupertino, CA 95014 USA

来源：

ACM COMPUTING SURVEYS | 2023年 / 55卷 / 12期

关键词：

Graph partitioning; hypergraph partitioning; load balancing; COMMUNICATION-COST METRICS; GRAPH; ALGORITHM; MATRICES; MODEL; EIGENVECTORS; PERFORMANCE;

D O I：

10.1145/3571808

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the past decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic [29]. In particular, the survey extends the previous survey by also covering hypergraph partitioning and has an additional focus on parallel algorithms.

引用

页数：38

共 193 条

[1] Sphynx: A parallel multi-GPU graph partitioner for distributed-memory systems [J].

Acer, Seher ;

Boman, Erik G. ;

Glusa, Christian A. ;

Rajamanickam, Sivasankaran .

PARALLEL COMPUTING, 2021, 106

[2] SPHYNX: Spectral Partitioning for HYbrid aNd aXelerator-enabled systems [J].

Acer, Seher ;

Boman, Erik G. ;

Rajamanickam, Sivasankaran .

2020 IEEE 34TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW 2020), 2020, :440-449

[3] High-Quality Shared-Memory Graph Partitioning [J].

Akhremtsev, Yaroslav ;

Sanders, Peter ;

Schulz, Christian .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2020, 31 (11) :2710-2722

[4]

Akhremtsev Yaroslav., 2017, 2017 P NINTEENTH WOR, P28, DOI [DOI 10.1137/1.9781611974768.3, 10.1137/1.9781611974768.3]

[5]

Alpert C. J., 1998, ISPD-98. 1998 International Symposium on Physical Design, P80, DOI 10.1145/274535.274546

[6]

ALPERT CJ, 1995, DES AUT CON, P195

[7] Multilevel circuit partitioning [J].

Alpert, CJ ;

Huang, JH ;

Kahng, AB .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1998, 17 (08) :655-667

[8] RECENT DIRECTIONS IN NETLIST PARTITIONING - A SURVEY [J].

ALPERT, CJ ;

KAHNG, AB .

INTEGRATION-THE VLSI JOURNAL, 1995, 19 (1-2) :1-81

[9] The Complexity of Tree Partitioning [J].

An, Zhao ;

Feng, Qilong ;

Kanj, Iyad ;

Xia, Ge .

ALGORITHMICA, 2020, 82 (09) :2606-2643

[10] Memetic Multilevel Hypergraph Partitioning [J].

Andre, Robin ;

Schlag, Sebastian ;

Schulz, Christian .

GECCO'18: PROCEEDINGS OF THE 2018 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2018, :347-354

← 1 2 3 4 5 6 7 8 9 10 →