Vertex Ordering, Clustering, and Their Application to Graph Partitioning

被引：0

作者：

Yoon, Yourim ^{[1
]}

Kim, Yong-Hyuk ^{[2
]}

机构：

[1] LG Elect, Future IT R&D Lab, Seoul 137724, South Korea

[2] Kwangwoon Univ, Dept Comp Sci & Engn, Seoul 139701, South Korea

来源：

APPLIED MATHEMATICS & INFORMATION SCIENCES | 2014年 / 8卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

graph algorithms; design of algorithms; graph partitioning; vertex ordering; graph clustering; genetic algorithm;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We propose a new heuristic for vertex ordering and a method that splits the vertex ordering into clusters. We apply them to the graph partitioning problem. The application of these ideas incorporates reordering in genetic algorithms and the identification of clustered structures in graphs. Experimental tests on benchmark graphs showed that the new vertex-ordering scheme performed better than existing methods in terms of genetic algorithms, and that the clusters were successfully captured.

引用

页码：135 / 138

页数：4

共 50 条

[1] OPTIMAL VERTEX ORDERING OF A GRAPH AND ITS APPLICATION TO SYMMETRY DETECTION
JIANG, XY
BUNKE, H
LECTURE NOTES IN COMPUTER SCIENCE, 1992, 570 : 148 - 158
[2] Vertex separators for partitioning a graph
Evrendilek, Cem
SENSORS, 2008, 8 (02) : 635 - 657
[3] Clustering by vertex density in a graph
Guénoche, A
CLASSIFICATION, CLUSTERING, AND DATA MINING APPLICATIONS, 2004, : 15 - 23
[4] EFFICIENT GRAPH AUTOMORPHISM BY VERTEX PARTITIONING
FOWLER, G
HARALICK, R
GRAY, FG
FEUSTEL, C
GRINSTEAD, C
ARTIFICIAL INTELLIGENCE, 1983, 21 (1-2) : 245 - 269
[5] BOOTSTRAP CLUSTERING FOR GRAPH PARTITIONING
Gambette, Philippe
Guenoche, Alain
RAIRO-OPERATIONS RESEARCH, 2011, 45 (04) : 339 - 352
[6] Vertex Ordering Algorithms for Graph Coloring Problem
Kaya, Kamer
Demirel, Berker
Topal, Baris Batuhan
Asik, Arda
Demir, Ibrahim Bugra
2020 28TH SIGNAL PROCESSING AND COMMUNICATIONS APPLICATIONS CONFERENCE (SIU), 2020,
[7] Vertex Ordering Problems in Directed Graph Streams
Chakrabarti, Amit
Ghosh, Prantar
McGregor, Andrew
Vorotnikova, Sofya
PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), 2020, : 1786 - 1802
[8] Vertex Ordering Problems in Directed Graph Streams
Chakrabarti, Amit
Ghosh, Prantar
McGregor, Andrew
Vorotnikova, Sofya
PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2020, : 1786 - 1802
[9] Partitioning a graph into vertex-disjoint paths
Li, J
Steiner, G
STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2005, 42 (03) : 277 - 294
[10] A Graph Partitioning Algorithm for Edge or Vertex Balance
El Moussawi, Adnan
Seghouani, Nacera Bennacer
Bugiotti, Francesca
DATABASE AND EXPERT SYSTEMS APPLICATIONS, DEXA 2020, PT I, 2020, 12391 : 23 - 37

← 1 2 3 4 5 →