Jul 2026· International Symposium on Parallel and Distributed Computing· pp. 93-102· 0 citations· 62 references
Computer Science
Abstract
An independent set of an undirected graph is a subset of vertices where no two vertices included in the set are neighbors. A Maximal Independent Set (MIS) of a graph is an independent set such that no additional vertices can be added to the set without violating the requirements of an independent set. To support modern large graphs, parallel MIS algorithms and their multi-core, GPU, and distributed memory implementations have attracted widespread research interests in recent years. We present a distributed MIS solution to support applications that demand high throughput and scalability. Our solution is designed to support various randomized priority assignment techniques and to compute MIS in a fully asynchronous or round-synchronous manner, the latter is required by some priority assignment techniques. Our MPI-based prototype attains strong scaling by way of multilevel load-balanced graph partitioning, accelerates distributed processing through computationcommunication overlap and message prioritization, and produces deterministic results. We demonstrate scalability using massive datasets: e.g., a real-world web graph with 128 billion edges and 512 compute nodes (16 K CPU-cores), and competitiveness of our solution through empirical comparisons: our implementation comfortably outperforms both CombBLAS-MIS and AGM-MIS, and identifies MIS' of size comparable to those of the key parallel and distributed solutions found in the literature.
The results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 × , respectively, while maintaining comparable or superior solution quality.
Joseph Nke, Seunghwa Kang, Brad Rees et al.· International Conference on...· 0 citations
This work presents a novel algorithm named HP-MC that, like prior approaches, is based on the branch and bound search, but which outperforms the leading maximum clique codes on large sparse graphs of various topologies by up to 10x on average.
This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.
This survey will help researchers better understand and gain useful insights into the large and complex design space of out-of-core graph processing, including graph preprocessing, graph algorithm execution, utilization of emerging storage devices, and miscellaneous optimizations.
Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations
This paper presents four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch when a batch of edges are inserted or deleted.
Abhijeet Sahu, Harmit Singh, Soham Nandy et al.· IEEE International Symposium...· 0 citations