Fully Dynamic Rooted Spanning Tree on GPU

Abhijeet Sahu; G. Ramakrishna; Harmit Singh; Soham Nandy

REVIEW 4 major objections 5 minor 19 references

Fully Dynamic Rooted Spanning Tree on GPU

T0 review · 4 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Four GPU algorithms update a rooted spanning forest under batch edge changes without rebuilding it.

desk verdict First serious GPU batch-dynamic rooted spanning forest work with strong speedups, but the deletion pseudocode detaches vertices for non-tree edges while the proof only covers tree edges; that gap needs to be fixed before the results can be trusted. read the letter →

arxiv 2607.20211 v1 pith:7NSSTEHR submitted 2026-07-22 cs.DC cs.DS

Abhijeet Sahu , Harmit Singh , Soham Nandy , G. Ramakrishna This is my paper · ORCID

classification cs.DCcs.DS

keywords dynamicspanningtreeGPUalgorithmbatchupdatesrootedforestEulertourhookingandshortcuttingsupergraphpathreversal

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that a rooted spanning forest can be maintained dynamically on a GPU: when a batch of edges is inserted or deleted, the forest is repaired locally rather than recomputed from scratch. It splits the repair into two subtasks — finding oriented replacement edges that reconnect the forest, and reversing the orientation of selected tree paths to accept those edges — and gives four parallel algorithms, each pairing a method for one subtask with a method for the other. If correct, an update that would cost a full graph traversal becomes a polylogarithmic-depth pass, and experiments on large real-world graphs report millions of updates per second, with speedups of hundreds to thousands over static GPU BFS.

What carries the argument

The load-bearing mechanism is the interval test in Algorithm 3: using Euler-tour start and finish times, a vertex u is judged to lie on the path from x to the tree's root r exactly when start[r] < start[u] ≤ start[x] and finish[r] > finish[u] ≥ finish[x]. This test lets all affected paths be reversed in parallel, and its correctness determines whether parent pointers are flipped correctly. The supporting machinery is the generic split into oriented replacement edges (via a supergraph of connected components or via hooking-shortcutting on component representatives) and path reversal (via broadcasting or the Euler tour).

What would settle it

Run Algorithm 3 on a small rooted tree with a known path and check whether the set of flipped parent edges exactly matches that path — any mismatch, such as flipping an off-path vertex or missing an on-path vertex, would show the interval condition is unsound. A broader test applies the full pipeline to a random graph with a batch of deletions and compares the resulting forest against a static spanning-tree computation on the updated graph.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that fully dynamic batch updates to a rooted spanning forest are practical on GPUs. The central idea is a generic algorithm that, after a batch update, finds a set of oriented replacement edges that reconnect the forest's components, then reverses the parent-child orientation along selected paths so the new edges can be attached without creating cycles. Two techniques are offered for each subtask: Supergraph and Hooking-Shortcutting for finding replacement edges, and Broadcasting and an Euler-Tour-based method for path reversal. The paper proves depth bounds — O(log n + log^2 k) for the Supergraph variants and O(log^2 n) for the Hooking-Shortcutting variant

Load-bearing premise

Everything hinges on the interval test — the claim that comparing Euler-tour start and finish times correctly identifies exactly which vertices lie on each path to the root; if the test is wrong for a single vertex, the parent flips can create a cycle or disconnect the forest.

Editorial extensions

If this is right

Batch updates to a spanning forest become polylogarithmic in depth, independent of the graph's diameter, so deep and large graphs can be updated quickly on GPUs.
The Euler-tour path-reversal variant uses O(V+E) space, whereas broadcasting needs O(V log V), making the Euler variant more practical for memory-bound GPUs.
The same pipeline can maintain connected components under dynamic insertions and deletions, not just spanning forests, as the paper notes.
The reported speedups suggest that dynamic repair, rather than static recomputation, is a viable strategy for evolving graphs with frequent small-to-moderate batch updates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The Euler-tour interval test is essentially an ancestor query; if it holds, it could be reused in other parallel path-reversal tasks, such as batch operations on link-cut trees or dynamic tree data structures.
The paper compares only against static baselines, so a head-to-head with a GPU-adapted hierarchical dynamic-connectivity algorithm would sharpen the practical claims.
Because deletions require scanning all non-tree edges to form the key-edge set, deletion cost scales with edge density; an extension that restricts the scan to components that actually split could improve dense-graph performance.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is the first serious attempt at GPU batch-dynamic rooted spanning forest maintenance, and it ships code and large speedups. But the deletion algorithm as written has a load-bearing correctness gap: it detaches vertices for every edge in the delete batch, while the proof only covers tree edges. That needs to be settled before the headline numbers can be trusted.

What is actually new: combining supergraph/Hooking-Shortcutting for oriented replacement edges with Broadcasting/Euler-tour path reversal on GPU. The Euler-tour path-reversal subroutine is a real design change from prior multicore work. The experiments cover 13 graphs up to ~1B edges, compare against static BFS and a ported PR-RST, and the HS/SG tradeoff analysis in Section V-D is sensible. Public code helps.

Soft spots, in proportion: 1. Algorithm 1, Lines 4-6, executes parent[u] = u for every (u,v) in B. If (u,v) is non-tree, v is not parent[u], and u gets detached from its tree. Their delete batches deliberately contain 60-70% non-tree edges (Section V-A), so this is not a corner case. Theorem 1's proof only considers tree-edge deletion. Either the code has a tree-edge guard the paper fails to show, or the algorithm corrupts the forest. This is the main blocker. 2. Lemma 4's proof is a single paragraph with inconsistent first/last vs start/finish notation and does not rigorously show the interval condition matches path membership. The interval test in Algorithm 3 is central, so this needs a real proof. 3. Theorems 3 and 4 state depth/work bounds without proof. They may be right, but "we analyze" followed by a statement with no argument is not enough. 4. The hash-table race condition in Section III-A is hand-waved ("eventually no two pairs have same key"). Unspecified races are a red flag for GPU code. 5. Experiments compare only against static baselines and report no variance bars. Given 25 runs, showing distributions or at least min/max would strengthen the claims. The speedups over static recomputation are expected, but the trend across batch sizes is still informative.

Bottom line: the core idea is plausible and likely salvageable, but as submitted the deletion correctness is not established. This deserves a serious referee, but the authors need to fix the pseudocode/proof mismatch, prove the interval condition, and provide proofs for the complexity theorems. I would not cite it in its current form.

Referee Report

4 major / 5 minor

Summary. The paper defines the D-RSF problem (batch insertion/deletion of edges in an undirected graph while maintaining a rooted spanning forest) and presents four GPU parallel algorithms: SG-ET, SG-BC, HS-ET, and HS-BC. The generic algorithm (Algorithm 1) repairs the existing forest by computing oriented replacement edges using either a supergraph or hooking-shortcutting, then reverses paths using either an Euler-tour or broadcasting subroutine. The authors claim depth bounds O(log n + log^2 k) and O(log^2 n), O(V+E) space for the ET variants, and report throughputs of 2 million insertions and 1.4 million deletions per second on an A100, with up to 900x/500x speedups over static GPU BFS.

Significance. If the correctness and complexity claims held, this would be a useful systems contribution: it appears to be among the first GPU implementations of batch-dynamic spanning-forest maintenance, the implementation is publicly available, and the evaluation is reasonably broad (13 graphs, several batch sizes, comparisons against static BFS and PR-RST). The algorithms are parameter-free and the engineering story (repair instead of recompute) is coherent. However, the manuscript currently does not deliver the formal guarantees it advertises: the deletion loop in the pseudocode is incorrect as written, and the proofs of path reversal and of the main depth theorems are incomplete. These are load-bearing for the central claims, so the paper cannot be accepted in its present form.

major comments (4)

[Algorithm 1, Lines 4-5; Theorem 1; Section V-A] The deletion loop iterates over every edge (u,v) in B and unconditionally executes parent[u]=u. Section V-A states that delete batches deliberately contain 60-70% non-tree edges. For a non-tree edge, v is not parent[u], so line 5 turns u into an artificial root and fragments F beyond the actual tree-edge deletions. The proof of Theorem 1 only treats tree-edge deletion, and Line 3 already removes these non-tree edges from the key-edge set M, so the algorithm never repairs the artificial components. Please add a tree-edge guard in the pseudocode and proof, or explain why line 5 is safe. This is load-bearing for the full-dynamic deletion claim.
[Lemma 4; Algorithm 3] The correctness proof of the Euler-tour path reversal is a hand-wave. It uses first[x_i], first[u_i], last[x_i], last[v_i], while Algorithm 3 defines start/finish, and no connection between the two notations is given. The statement Path(x_i,y_i)=U intersection V is asserted without proof. In a rooted Euler tour the interval condition can be made correct, but the paper must prove it for leaves, roots, and intermediate vertices, and must also argue that the parallel loop at Lines 13-17 reverses exactly the edges on the path and no others. All four algorithms depend on REVERSEPATHS, so this is central.
[Theorems 2-4; Section IV] Theorems 3 and 4, which state the depth and work guarantees for all four algorithms, are presented with no proofs. Theorem 2 also states the O(log n) depth and O(n) work of Algorithm 3 without proof. These theorems support Table I and the abstract's complexity claims. Please provide proofs or at least a detailed derivation showing how the subroutines' depths compose for each of the four algorithms.
[Section III-A; hash-table construction] The supergraph method relies on the assertion that 'eventually no two pairs in the hash table have same key, due to race conditions.' This is an unverified concurrency assumption. Since an arbitrary representative edge between the same pair of trees is sufficient for connectivity, the assumption may be acceptable, but it should be stated explicitly and justified, or the implementation should use deterministic duplicate elimination so correctness does not rest on undefined GPU write races.

minor comments (5)

[Table I; References] Reference [10] is cited as 'HDT', but the reference list entry is Acar et al., 'Parallel batch-dynamic graph connectivity'. The Holm-de Lichtenberg-Thorup paper is not cited. Please fix the attribution.
[Lemma 4; Algorithm 3] Notation is inconsistent: the proof uses first/last, while the algorithm uses start/finish. Also, 'firstEdge' and 'lastEdge' are not formally defined. Please align the notation and define the Euler-tour edge ordering used.
[Figure/table numbering] There are numbering inconsistencies: Section V-C refers to Figure 5 for runtime, but Figure 5 appears after the discussion of speedups; check all figure references. Also, Section V-B states 'by by Cong et al.' - typo.
[Algorithm 3, Line 15] The strict vs. non-strict inequalities in the interval test should be explained. In particular, the condition excludes the root r, which is correct for path reversal, but the lemma statement and proof should make this precise.
[Section V-A] The sentence describing the composition of delete batches could be clarified: it should say explicitly that the remaining 60-70% are non-tree edges, and explain how this interacts with the pseudocode of Algorithm 1.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivation rests on cited external primitives and structural arguments; the sole self-citation is motivational, not load-bearing.

full rationale

The paper contains no fitting of parameters that are later renamed as predictions, no uniqueness theorem imported from the authors' prior work, and no definition that presupposes the target result. The four algorithms are constructive: replacement edges are selected either by a supergraph construction or by Hooking-Shortcutting, and path reversal uses Broadcasting or an Euler-tour rank test, with the underlying primitives cited to external sources ([5], [6], [16]) rather than to the authors' own prior results. Theorems 1 and 2 and Lemmas 1-4 argue from the forest structure and from those cited primitives; the claimed O(log n + log^2 k) depths and O(V+E) space are derived from those lemmas, not assumed. The experimental speedups and throughput are measurements against static baselines, not predictions extracted from a fitted model. The only self-citation is [3] (Haryan et al., which includes co-author G. Ramakrishna), used in the introduction and related work to motivate dynamic biconnected-component maintenance and to note that sparsification underperforms in practice; this citation is not load-bearing for the derivation. The Euler-tour interval condition in Algorithm 3/Lemma 4 is underproved, and Algorithm 1's deletion loop appears to detach vertices for non-tree edges in the pseudocode, but these are correctness risks, not circularity: they do not make the output equivalent to the input by construction. Accordingly, the score is 1 for a minor, non-load-bearing self-citation, not for any circular derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities. The paper's contribution is algorithmic, built from cited primitives (HS, Broadcasting, Euler Tour). The main unexamined assumptions are the seeded HS variant and the racy hash-table behavior.

assumptions (4)

domain assumption The GPU Hooking-Shortcutting routine from Soman et al. [16] yields a valid spanning forest when seeded with an existing partial forest.
Algorithm 2 (Phase 1) relies on this to produce replacement edges; the paper does not re-derive or test the seeded variant.
standard math The Euler Tour Technique of Polak et al. [5] computes correct rank/start/finish values for rooted trees.
Algorithm 3 uses these times to characterize paths; accepted as a known algorithm.
standard math Broadcasting path reversal from Cong and Bader [6] reverses all paths in R within O(log n) depth.
Lemma 3 cites [6]; used by SG-BC and HS-BC.
ad hoc to paper Concurrent writes to the GPU hash table for duplicate keys settle on exactly one value per key without corrupting the table.
Section III-A states 'eventually no two pairs in the hash table have same key, due to race conditions'; no atomic protocol is specified, so this is an unverified implementation assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fully Dynamic Rooted Spanning Tree on GPU." pith.science (2026). https://pith.science/paper/7NSSTEHR

@misc{pith2026260720211,
  author       = {Pith},
  title        = {Pith review of: Fully Dynamic Rooted Spanning Tree on GPU},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7NSSTEHR}},
  note         = {Machine review of arXiv:2607.20211}
}

read the original abstract

Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimum-weighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms.

Figures

Figures reproduced from arXiv: 2607.20211 by the authors.

**Figure 1.** Overview of the D-RSF algorithm. (a) The black solid lines represent the rooted spanning forest, while the blue edges denote the key edges. (b) Replacement edges are selected from the key edges and oriented appropriately. (c) Parents are updated for affected vertices during path reversal to obtain an updated rooted spanning forest. B. Overview We now present a high-level overview of our generic parallel algorithm to… view at source ↗

**Figure 2.** Orientation of affected edges, show in solid thick, is reversed. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Speedup: Our algorithms w.r.t static GPU BFS for insert ponents using the method described in [16]. We subsequently use stream compaction to select all unique representatives and apply parallel BFS starting from these representatives. Our results show a maximum speedup of 530× for edge deletion (with an average speedup of 160×) and 900× for edge insertion (with an average speedup of 200×), as illustrated in Figures … view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Speedup: Our algorithms w.r.t static GPU BFS for delete (maximum 30×) and an 18× speedup for insertions (maximum 41×). This performance gap is largely due to the fact that PR-RST is a static algorithm that recomputes the entire rooted spanning forest after every updat…

**Figure 5.** Figure 5: The results demonstrate that our algorithms maintain [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 5.** Figure 5: Runtime comparison of baseline and proposed algorithms across various batches for (a) Deletion operation and (b) Insertion operation. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

**Figure 6.** Figure 6: HS performance depends on the number of nodes ( [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references

[1]

The future is big graphs: a community view on graph processing systems,

S. Sakr, A. Bonifati, H. V oigt, A. Iosup, K. Ammar, R. Angles, W. Aref, M. Arenas, M. Besta, P. A. Bonczet al., “The future is big graphs: a community view on graph processing systems,”Communications of the ACM, vol. 64, no. 9, pp. 62–71, 2021

2021
[2]

A shared-memory algorithm for updating tree-based properties of large dynamic networks,

S. Srinivasan, S. D. Pollard, B. Norris, S. K. Das, and S. Bhowmick, “A shared-memory algorithm for updating tree-based properties of large dynamic networks,”IEEE Transactions on Big Data, vol. 8, no. 2, pp. 302–317, 2018. 102 103 104 105 32 64 CO 102 103 104 105 128 256 512 1024 2048 UK-05 102 103 104 105 64 128 256 512 1024 RU 102 103 104 105 8 32 128 5...

2018
[3]

Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components,

C. A. Haryan, G. Ramakrishna, K. Kothapalli, and D. S. Banerjee, “Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components,” inInternational Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2022, pp. 1195–1205

2022
[4]

Scalable gpu graph traver- sal,

D. Merrill, M. Garland, and A. Grimshaw, “Scalable gpu graph traver- sal,”ACM Sigplan Notices, vol. 47, no. 8, pp. 117–128, 2012

2012
[5]

Euler meets gpu: practical graph algorithms with theoretical guarantees,

A. Polak, A. Siwiec, and M. Stobierski, “Euler meets gpu: practical graph algorithms with theoretical guarantees,” in2021 IEEE Interna- tional Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2021, pp. 233–244

2021
[6]

The euler tour technique and parallel rooted spanning tree,

G. Cong and D. A. Bader, “The euler tour technique and parallel rooted spanning tree,” inInternational Conference on Parallel Processing,
[7]

Sparsifica- tion—a technique for speeding up dynamic graph algorithms,

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, “Sparsifica- tion—a technique for speeding up dynamic graph algorithms,”Journal of the ACM (JACM), vol. 44, no. 5, pp. 669–696, 1997

1997
[8]

Application of graph sparsifi- cation in developing parallel algorithms for updating connected compo- nents,

S. Srinivasan, S. Bhowmick, and S. Das, “Application of graph sparsifi- cation in developing parallel algorithms for updating connected compo- nents,” in2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 2016, pp. 885–891

2016

Show all 19 references

[9]

A new parallel algorithm for connected components in dynamic graphs,

R. McColl, O. Green, and D. A. Bader, “A new parallel algorithm for connected components in dynamic graphs,” in20th Annual International Conference on High Performance Computing. IEEE, 2013, pp. 246– 255

2013
[10]

Parallel batch-dynamic graph connectivity,

U. A. Acar, D. Anderson, G. E. Blelloch, and L. Dhulipala, “Parallel batch-dynamic graph connectivity,” inThe 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019, pp. 381–392

2019
[11]

Towards scalable and practical batch-dynamic connectivity,

Q. De Man, L. Dhulipala, A. Karczmarz, J. Łkacki, J. Shun, and Z. Wang, “Towards scalable and practical batch-dynamic connectivity,” inProceedings of the 3rd Highlights of Parallel Computing Workshop, 2025, pp. 16–18

2025
[12]

A data structure for dynamic trees,

D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees,” inProceedings of the thirteenth annual ACM symposium on Theory of computing, 1981, pp. 114–122

1981
[13]

Data structures for on-line updating of minimum spanning trees,

G. N. Frederickson, “Data structures for on-line updating of minimum spanning trees,” inProceedings of the fifteenth annual ACM symposium on Theory of computing, 1983, pp. 252–257

1983
[14]

Randomized fully dynamic graph algorithms with polylogarithmic time per operation,

M. R. Henzinger and V . King, “Randomized fully dynamic graph algorithms with polylogarithmic time per operation,”Journal of the ACM (JACM), vol. 46, no. 4, pp. 502–516, 1999

1999
[15]

Batch-parallel euler tour trees,

T. Tseng, L. Dhulipala, and G. Blelloch, “Batch-parallel euler tour trees,” in2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2019, pp. 92–106

2019
[16]

A fast gpu algorithm for graph connectivity,

J. Soman, K. Kishore, and P. Narayanan, “A fast gpu algorithm for graph connectivity,” in2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, 2010, pp. 1–8

2010
[17]

Layered label propaga- tion: A multiresolution coordinate-free ordering for compressing social networks,

P. Boldi, M. Rosa, M. Santini, and S. Vigna, “Layered label propaga- tion: A multiresolution coordinate-free ordering for compressing social networks,” inProceedings of the 20th international conference on World Wide Web, 2011, pp. 587–596

2011
[18]

Snap: A general-purpose network analysis and graph-mining library,

J. Leskovec and R. Sosi ˇc, “Snap: A general-purpose network analysis and graph-mining library,”ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 1, pp. 1–20, 2016

2016
[2004]

ICPP 2004.IEEE, 2004, pp. 448–457

2004

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

The future is big graphs: a community view on graph processing systems,

S. Sakr, A. Bonifati, H. V oigt, A. Iosup, K. Ammar, R. Angles, W. Aref, M. Arenas, M. Besta, P. A. Bonczet al., “The future is big graphs: a community view on graph processing systems,”Communications of the ACM, vol. 64, no. 9, pp. 62–71, 2021

2021

[2] [2]

A shared-memory algorithm for updating tree-based properties of large dynamic networks,

S. Srinivasan, S. D. Pollard, B. Norris, S. K. Das, and S. Bhowmick, “A shared-memory algorithm for updating tree-based properties of large dynamic networks,”IEEE Transactions on Big Data, vol. 8, no. 2, pp. 302–317, 2018. 102 103 104 105 32 64 CO 102 103 104 105 128 256 512 1024 2048 UK-05 102 103 104 105 64 128 256 512 1024 RU 102 103 104 105 8 32 128 5...

2018

[3] [3]

Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components,

C. A. Haryan, G. Ramakrishna, K. Kothapalli, and D. S. Banerjee, “Shared-memory parallel algorithms for fully dynamic maintenance of 2-connected components,” inInternational Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2022, pp. 1195–1205

2022

[4] [4]

Scalable gpu graph traver- sal,

D. Merrill, M. Garland, and A. Grimshaw, “Scalable gpu graph traver- sal,”ACM Sigplan Notices, vol. 47, no. 8, pp. 117–128, 2012

2012

[5] [5]

Euler meets gpu: practical graph algorithms with theoretical guarantees,

A. Polak, A. Siwiec, and M. Stobierski, “Euler meets gpu: practical graph algorithms with theoretical guarantees,” in2021 IEEE Interna- tional Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2021, pp. 233–244

2021

[6] [6]

The euler tour technique and parallel rooted spanning tree,

G. Cong and D. A. Bader, “The euler tour technique and parallel rooted spanning tree,” inInternational Conference on Parallel Processing,

[7] [7]

Sparsifica- tion—a technique for speeding up dynamic graph algorithms,

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, “Sparsifica- tion—a technique for speeding up dynamic graph algorithms,”Journal of the ACM (JACM), vol. 44, no. 5, pp. 669–696, 1997

1997

[8] [8]

Application of graph sparsifi- cation in developing parallel algorithms for updating connected compo- nents,

S. Srinivasan, S. Bhowmick, and S. Das, “Application of graph sparsifi- cation in developing parallel algorithms for updating connected compo- nents,” in2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 2016, pp. 885–891

2016