Name
Abstract | ||
|---|---|---|
A balanced graph partition on a vertex-weighted graph is a partition of the vertex set such that the partition has k parts and the disparity, which is defined as the ratio of the maximum total weight of parts to the minimum one, is at most r. In this paper, a novel algorithm is proposed that enumerates all the graph partitions with small disparity. Experimental results show that five millions of partitions with small disparity for some graph with more than 100 edges can be enumerated within ten minutes. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-53925-6_10 | WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017 |
Field | DocType | Volume |
Discrete mathematics,Strength of a graph,Combinatorics,Vertex (geometry),Computer science,Simplex graph,Null graph,Partition (number theory),Graph partition,Voltage graph,Complement graph | Conference | 10167 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.36 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun Kawahara | 1 | 34 | 8.82 |
| Takashi Horiyama | 2 | 81 | 19.76 |
| K. Hotta | 3 | 3 | 0.76 |
| Shin-ichi Minato | 4 | 725 | 84.72 |