wolfram77

I made this wishlist in around 2019-20.

wolfram77

I made this wishlist in around 2019-20.

wolfram77

I made this wishlist in around 2019-20.

wolfram77

I made this wishlist in around 2019-20.

wolfram77

Obtained this list after scanning (manually, unfortunately) Google Scholar for several pages.

wolfram77

My notes below.

wolfram77

My notes below.

wolfram77

Lu, H., Halappanavar, M., Chavarria-Miranda, D., Gebremedhin, A. H., Panyala, A., & Kalyanaraman, A. (2016). Algorithms for balanced graph colorings with applications in parallel computing. IEEE Transactions on Parallel and Distributed Systems, 28(5), 1240-1256.

In this paper, Lu et al. present parallel approaches for balanced graph coloring. Graph coloring is an important problem in parallel computing, where the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color. It is an NP-hard problem because, given a coloring, it is easy to verify if it is valid, but one cannot confirm whether a coloring is optimal in polynomial time. Graph coloring has applications in scheduling, register allocation, scheduling and timetabling problems - or scheduling garbage collecting trucks in New York City.

Graph coloring is used to identify subsets of independent tasks in parallel computing, where each task can be executed without interference from others. How

wolfram77

Lu, H., Halappanavar, M., & Kalyanaraman, A. (2015). Parallel heuristics for scalable community detection. Parallel Computing, 47, 19-37.

In the paper, Lu et al. discuss why parallel community detection may cause negative modularity gain - this happens in cases when two disconnected nodes join the same community with little affinity to the community they are moving to. It is also possible that the modularity gain estimated by a parallel algorithm is lower that the actual gain - this can happen when two nodes are connected, and move to the same community.

Lu et al. also introduce the singlet minimum label heuristic to prevent vertex swapping. They also propose the generalized minimum label heuristic, where a vertex is moved to the community with the highest modularity gain, but with the smallest label (if multiple communities have the same gain). They also discuss distance-1 coloring as a way to prevent vertex swapping, where only vertices with the same color are processed in parallel.

wolfram77

My highlighted notes for the following paper:

Ye, C., Li, Y., He, B., Li, Z., & Sun, J. (2023). Large-scale graph label propagation on gpus. IEEE Transactions on Knowledge and Data Engineering, 36(10), 5234-5248.