Comments:

Nice coarse-gaining based heuristic to partition the nodes into k sets of similar sizes minimizing the number of edges between those sets. Random maximal matchings are used to coarse-grain the graph. Maybe fast heuristics to obtain a large maximal matching can be considered, such as using the two rules detailed here: [Karp-Sipser based kernels for bipartite graph matching](https://papers-gamma.link/paper/160). Publicly available implementation: http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
Maximimi at 2020-06-12 13:32:46
Edited by Maximimi at 2020-06-12 20:57:05

Please consider to register or login to comment on the paper.