Name
Abstract | ||
|---|---|---|
Most of previous genetic algorithms for solving graph problems have used vertex-based encoding. In this paper, we introduce spanning tree-based encoding instead of vertex-based encoding for the well-known MAX CUT problem. We propose a new genetic algorithm based on this new type of encoding. We conducted experiments on benchmark graphs and could obtain performance improvement on sparse graphs, which appear in real-world applications such as social networks and systems biology, when the proposed methods are compared with ones using vertex-based encoding. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-32937-1_51 | PPSN (1) |
Keywords | Field | DocType |
max cut problem,vertex-based encoding,tree-based encoding,new type,benchmark graph,real-world application,performance improvement,social network,previous genetic algorithm,new genetic algorithm,evolutionary search,graph problem,graph,encoding,genetic algorithm,max cut,representation,spanning tree | Mathematical optimization,Minimum degree spanning tree,Vertex (geometry),Prim's algorithm,Computer science,Spanning tree,Gomory–Hu tree,Maximum cut,Feedback vertex set,Minimum spanning tree | Conference |
Citations | PageRank | References |
1 | 0.35 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kisung Seo | 1 | 141 | 18.95 |
| Soohwan Hyun | 2 | 24 | 4.18 |
| Yong-Hyuk Kim | 3 | 355 | 40.27 |