Pith. sign in

REVIEW 4 major objections 5 minor 42 references

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees

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

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

Pith's one-line read A batch-dynamic data structure maintains approximate coreness with worst-case polylog work per batch.

desk verdict A credible and genuinely novel worst-case strengthening of Liu et al., with one load-bearing deletion-phase lemma that needs a full proof before I'd fully sign off. read the letter →

arxiv 2507.06334 v1 pith:ISZ4JCF6 submitted 2025-07-08 cs.DS

Mohsen Ghaffari , Jaehyun Koo This is my paper · ORCID
classification cs.DS MSC 68W1005C85
keywords corenessdecompositionk-corebatch-dynamicalgorithmsparallelgraphorientationarboricitydensestsubgraphworst-caseupdatetime
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

This paper establishes that approximate coreness decomposition can be maintained under large batches of edge insertions and deletions with a worst-case work bound of $b\cdot\mathrm{poly}(\log n)$ per batch and polylogarithmic depth, where $b$ is the batch size. Previous parallel batch-dynamic algorithms for this problem could only guarantee these bounds in amortized form, so individual batches could occasionally become expensive. The paper's main theorem keeps an estimate $\mathrm{core}_{ALG}(v)$ inside $[(1/2-\epsilon)\mathrm{core}(v),(2+\epsilon)\mathrm{core}(v)]$ with high probability for any $\epsilon\in(0,0.1)$. Because the same machinery maintains a low out-degree orientation, it also yields batch-dynamic approximations for density and arboricity and, as corollaries, maximal matching and vertex coloring with the same worst-case per-batch guarantees. A reader would care because worst-case bounds make dynamic data structures predictable for real-time systems and usable in static algorithms that revisit each part only once.

What carries the argument

The central object is an $H$-balanced orientation, a directed version of the graph in which every edge $(u\to v)$ satisfies $\min(\delta^+(u),H)\le\min(\delta^+(v),H)+1$, so out-degrees change by at most one along edges and the maximum out-degree is capped near $H$; Lemmas 3.4 and 3.5 show that in such an orientation each vertex's out-degree is within a constant factor of its coreness unless both are near the cap $H$. The batch-dynamic maintenance is carried by token bundles: a batch of updates is decomposed into bundles in which each vertex starts with at most one token, and a phase-parallel token-dropping game (for insertions) or token-pushing game (for deletions) moves tokens along edges until the orientation is balanced again. The key identity carrying the argument is the potential $\sum_v \mathrm{token}(v)\delta^+(v)$ that decreases by one with every legal token drop (or increases by one with every push), and the phase-counting lemmas bound each vertex's active phases by $O(H^2)$ and hence each batch by $O(H^3)$ phases; a further $O(H^2)$ rounds of extracting token bundles handle the general case. To cover arbitrary arboricity, the paper combines this with edge duplication and random sampling, since density, arboricity, and coreness concentrate under Bernoulli sampling.

What would settle it

Simulate the token-dropping algorithm on a graph with a small chosen height $H$ (say $H=2$ or $3$) and feed it an adversarial sequence of batches that repeatedly place a token at the same vertex while other tokens keep occupying its only downhill neighbor; count how many phases a single vertex is active. If any vertex is active more than $cH^2$ times for a fixed constant $c$, or a batch needs more than $cH^3$ phases, the phase-bound lemma behind the worst-case work guarantee is false.

Watch

Extended reading notes

Core claim

The paper claims to settle, up to logarithmic factors, the strongest natural per-batch guarantee for parallel dynamic coreness: every batch of $b$ insertions or deletions is processed in $\mathrm{poly}(\log n)$ depth and $O(b\,\mathrm{poly}(\log n))$ work, regardless of prior history. Concretely, Theorem 1.1 asserts a randomized data structure maintaining a $4+\epsilon$-approximation of coreness, equivalently $\mathrm{core}_{ALG}(v)\in[(1/2-\epsilon)\mathrm{core}(v),(2+\epsilon)\mathrm{core}(v)]$, with worst-case work $O(\epsilon^{-15}\log^9 n)$ per inserted edge and $O(\epsilon^{-13}\log^8 n)$ per deleted edge, and depth $O(\epsilon^{-12}\log^7 n)$ or $O(\epsilon^{-10}\log^6 n)$ per whole batch. This is the worst-case version of the earlier amortized parallel batch-dynamic algorithm [LSY+22b], with the same approximation guarantee. The path to the claim is to show that coreness can be read off the out-degrees of a suitably balanced orientation, and that such an orientation can be maintained batch-dynamically in worst-case polylogarithmic work per edge through parallel token-dropping and token-pushing games. The paper further claims the same orientation machinery yields $(1+\epsilon)$-approximate density, $(2+\epsilon)$-approximate arboricity, and a $(2+\epsilon)$-out-degree orientation, with corollaries for maximal matching and coloring.

Load-bearing premise

The load-bearing premise is that each token-dropping or token-pushing phase always makes enough progress, meaning every vertex is active at most $O(H^2)$ times and each batch finishes within $O(H^3)$ phases, so the clever charging arguments in the phase lemmas hold for every adversarial batch.

Editorial extensions

If this is right

  • With $p$ processors, each batch finishes in $\tilde{O}(b/p)$ time, matching the information-theoretic lower bound up to logarithmic factors.
  • The guarantee holds for every batch, so no update is ever much slower than the average, unlike the previous amortized algorithm; this is what real-time systems and one-pass static algorithms require.
  • The same balanced-orientation structure gives $(1+\epsilon)$-approximate density and arboricity and a $(2+\epsilon)$-out-degree orientation with worst-case per-batch work.
  • Maximal matching and both explicit and implicit vertex coloring inherit worst-case batch bounds from the orientation.
  • The approximation ratio matches the earlier amortized algorithm, so strengthening to worst-case does not degrade the quality of the maintained coreness.

Reading between the lines

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

  • If the phase lemmas are as strong as stated, the token-dropping and token-pushing template likely transfers to other monotone degree-based invariants, such as degeneracy orderings or $(p,q)$-core decompositions, whose potentials can be recharged per batch.
  • A natural stress test is to run the phase counter on an adversarial batch with $H=2$ or $H=3$; if any vertex is active more than $cH^2$ times for a fixed constant $c$, or any batch needs more than $cH^3$ phases, the charging argument behind the worst-case bound would need revision.
  • The sampling-based removal of the arboricity assumption is likely to port to other density measures that concentrate under subsampling, giving worst-case batch updates for objects such as $k$-clique density if a parallel counting oracle exists.
  • In practice the $\epsilon^{-15}$ dependence may dominate; a plausible engineering extension is to keep a coarse phase structure inside and reserve small $\epsilon$ only for the outer arboricity loop, testing whether the polylog exponents can be decoupled from $\epsilon$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper presents a parallel batch-dynamic data structure for maintaining approximate coreness decomposition with worst-case per-batch work, strengthening the amortized guarantees of Liu et al. (SPAA'22). The core technical contribution is a deterministic data structure Balanced(H) that maintains an H-balanced orientation under batches of edge insertions and deletions, with claimed worst-case work O(H^6 log n) per inserted edge and O(H^5 log n) per deleted edge and polylogarithmic depth. The balanced orientation is then connected to coreness, density, and arboricity via expansion arguments, and random sampling/duplication is used to remove any dependence on a known arboricity bound. Applications to maximal matching and explicit/implicit coloring are derived from the low-outdegree orientation interface.

Significance. If the technical claims hold, this is a substantial result: it provides the first parallel batch-dynamic coreness approximation with worst-case update work, resolving a gap left by the amortized SPAA'22 algorithm, and it also gives worst-case balanced-orientation, density, arboricity, matching, and coloring corollaries. The paper contains detailed data-structure implementations, potential-function arguments for the extraction procedure, and explicit sampling lemmas with Chernoff bounds. The main weakness is that the central phase-bound lemmas for the token-dropping and token-pushing games (Lemmas 4.8, 4.13, 4.18, 4.22) are only sketched, and the deletion-side Lemma 4.22 is the least secure point in the chain; the worst-case deletion bound of Theorem 4.1 and hence of Theorem 1.1 depends on it.

major comments (4)
  1. [§4.3.1, Lemma 4.22] The proof that every vertex is active O(H^2) times in the decremental token-pushing game is not sufficiently formal and is load-bearing for the worst-case deletion bound. The second-case argument says 'every vertex can send at most O(H) tokens since every vertex has at most H outgoing edges to receive one, plus the initial token', but this is not justified for real vertices once truncated ranks H+1 and transparent tokens are present: a real vertex can have more than H outgoing edges, and Remark 4.20's dummy-node reinterpretation is only described informally. The text does not prove that each failed receive at a real vertex can be charged injectively to a token-send by a lower occupied neighbor, nor that the accounting works across transparent and non-transparent tokens without double counting. Since Lemma 4.18 and the O(H^5 log n) deletion bound of Theorem 4.1 rest on this lemma, a complete charging proof is needed.
  2. [§4.2.1, Lemma 4.13] The analogous incremental active-vertex bound is also sketched rather than proved. The claim that a rejected proposal can happen at most O(H^2) times relies on the assertion that every node can receive at most O(H) tokens because it can send at most that many tokens through outgoing edges, plus store one. This requires a precise accounting over all phases: one must define when an outgoing edge is consumed, why a vertex cannot receive more than O(H) tokens even though its indegree may be large, and why the same rejecting neighbor cannot be charged multiple times through different edges without a global bound. The proof should be expanded because Lemma 4.8's O(H^3) phase bound depends on it.
  3. [§4.3.1, Lemmas 4.18 and 4.21] The proof of Lemma 4.18 states that the proof of Lemma 4.8 applies 'with small modifications', but the decremental setting changes the active-vertex definition and introduces transparent tokens through dummy nodes. It is not immediate that the extended traversal of a token is still well-defined, that its length is at most H when dummy nodes are introduced, or that Lemma 4.21 remains valid when a real vertex can hold a token while also receiving a transparent token. These steps need to be stated explicitly; as written, the O(H^3) phase bound for deletions is not fully established.
  4. [§4.2.2, Lemma 4.15] The potential-function argument for ExtractTokenBundle contains a wording error and a gap that matters for the insertion bound. The sentence 'As a vertex u began occupied and ended up empty' should describe a vertex that proposed a token and did not receive one, not an occupied vertex in the token-bundle sense. More substantively, the proof that |tight(u)| decreases when u does not receive a token must rule out that reversals of edges from other vertices or newly inserted edges create new tight outgoing edges for u; the claim that the RHS never decreases and the LHS stays unchanged is not enough unless one also observes that all new outgoing edges of u point to non-lower-level vertices. This should be made precise because Lemma 4.15 is what limits the number of ExtractTokenBundle iterations to O(H^2).
minor comments (5)
  1. [Definition 4.2] The rank is described as 'labeled from 1, 2, ..., n, if n is the number of outgoing edges', which reuses n for the outdegree of a vertex; use a different symbol such as d^+(v) to avoid confusion with the global vertex count.
  2. [Lemma 3.4 proof] The expansion argument defines S' as the set of predecessors of S, but then states 'all vertices w in S have delta^+(w) <= delta^+(v) + 2 log n / epsilon'; the inequality should be asserted for w in S', and the notation should be corrected.
  3. [Lemma 4.15 proof] The phrase 'As a vertex u began occupied and ended up empty' is confusing: a vertex in ExtractTokenBundle proposes a token and either receives one or not; the intended meaning is that u's proposal was rejected. The wording should be revised.
  4. [References] References [LSY+22a] and [LSY+22b] appear to be duplicate entries for the same paper; one of them should be removed or the citations should be unified.
  5. [Section 4.3.1, Lemma 4.23] In the implementation of a decremental phase, the sentence 'Processing the edges of truncated rank H+1 is not different since all the labels will be 0' is too terse: the labels of transparent edges are not always fixed during the phase, and the special handling deserves a few sentences of explanation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the coreness/density approximations are reduced to properties of a maintained H-balanced orientation via forward proofs from definitions, the Nash-Williams theorem, and Chernoff bounds; the worst-case work bounds are argued through token-dropping/pushing phase counting that does not import the target result.

full rationale

The paper's central chain treats the balanced-orientation data structure as the primitive and then derives coreness, density, and arboricity estimates from it. Lemmas 3.2, 3.4, and 3.5 prove inequalities relating max outdegree, per-vertex outdegree, density, arboricity, and coreness directly from the balancedness invariant and from the Nash-Williams characterization and the permutation definition of coreness; none of these lemmas assumes the approximation factor being proved. The maintenance of the H-balanced orientation in Section 4 is self-contained: the phase bounds (Lemmas 4.8, 4.13, 4.15, 4.18, 4.22) are proven by counting token movements, active-vertex visits, and a potential over tight edges, with the deletion side using a truncated-rank/dummy-node reinterpretation that is a bookkeeping device rather than a restatement of the update-work bound. The randomized-sparsification arguments in Section 5 and Appendix A use Chernoff bounds and concentration lemmas (A.1–A.4) that are independent of the maintained estimates, and Theorem 1.1's final estimate is obtained by sweeping powers of (1+ε) and picking a threshold from the maintained outdegree estimates; the interval for core(v) follows after the fact from Lemmas 3.4/3.5 and the concentration lemmas, not from the definition of coreALG. There is no fitted parameter that is later renamed a prediction, no uniqueness claim imported from the authors' own prior work, and no load-bearing ansatz smuggled in through self-citation; the only cited algorithmic inspiration (Liu et al. SPAA'22, Brandt et al. SPAA'21, Sawlani–Wang, Brodal–Fagerberg) is external and is used as a benchmark or as a framework to be adapted, not as the source of the paper's conclusions. The most delicate steps—especially the deletion-phase active-vertex bound in Lemma 4.22 and the transparent-token handling in Remark 4.20—are intricate and may warrant careful verification, but intricacy is a correctness risk, not circularity. Accordingly, no circular step is exhibited, and the derivation chain is not equivalent to its inputs by construction.

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

The central claim rests on standard mathematical tools (Chernoff, Nash-Williams, parallel dictionary structures) and the CRCW PRAM model. No free parameters are fitted to data; parameters such as H, epsilon, B, and K are algorithmic inputs or derived constants. No new physical or testable entities are introduced: tokens, token bundles, and dummy nodes are internal proof devices, not independently observable constructs.

assumptions (4)
  • standard math Chernoff bound for sums of independent Bernoulli variables (Theorem 2.7)
    Used throughout the randomized sampling arguments in Appendix A and in the palette-based coloring proofs.
  • standard math Nash-Williams theorem characterizing arboricity via edge counts (Lemma 2.5)
    Links arboricity to maximizing |E[S]|/(|S|-1), used in Corollary 3.3 and Lemma A.3.
  • standard math Parallel red-black tree of [PP01] supports batch operations in O(log n) work per element and O(log n) depth; parallel hash table of [GMV91] in O(1) work per element and O(log^* n) depth
    These are assumed data structure primitives underlying all stated work and depth bounds.
  • domain assumption Shared-memory CRCW PRAM as the computation model, with EREW simulation at O(log n) overhead (Section 1.1)
    The parallel complexity claims are model-dependent and rely on this standard assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees." pith.science (2026). https://pith.science/paper/ISZ4JCF6

@misc{pith2026250706334,
  author       = {Pith},
  title        = {Pith review of: Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ISZ4JCF6}},
  note         = {Machine review of arXiv:2507.06334}
}
abstract

We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our algorithm processes all these updates in $ \text{poly}(\log n)$ depth, using a worst-case work bound of $b\cdot \text{poly}(\log n)$ where $b$ denotes the batch size. This means the batch gets processed in $\tilde{O}(b/p)$ time, given $p$ processors, which is optimal up to logarithmic factors. Previously, an algorithm with similar guarantees was known by the celebrated work of Liu, Shi, Yu, Dhulipala, and Shun [SPAA'22], but with the caveat of the work bound, and thus the runtime, being only amortized.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 30 canonical work pages

  1. [1]

    Parallel batch-dynamic trees via change propagation

    Umut Acar and Daniel Anderson. Parallel batch-dynamic trees via change propagation. In European Symposium on Algorithms (ESA) , 2020

    2020

  2. [2]

    Parallel batch-dynamic graph connectivity

    Umut A Acar, Daniel Anderson, Guy E Blelloch, and Laxman Dhulipala. Parallel batch-dynamic graph connectivity. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures , pages 381--392, 2019

    2019

  3. [3]

    Deterministic and low-span work-efficient parallel batch-dynamic trees

    Daniel Anderson and Guy E Blelloch. Deterministic and low-span work-efficient parallel batch-dynamic trees. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages 247--258, 2024

    2024

  4. [4]

    Large scale networks fingerprinting and visualization using the k-core decomposition

    J Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in neural information processing systems , 18, 2005

    work page 2005

  5. [5]

    Dynamic representations of sparse graphs

    Gerth St lting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In Workshop on Algorithms and Data Structures , pages 342--351. Springer, 1999

    work page 1999

  6. [6]

    Core decomposition of uncertain graphs

    Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. Core decomposition of uncertain graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 1316--1325, 2014

    work page 2014

  7. [7]

    Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams

    Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 173--182, 2015

    work page 2015

  8. [8]

    Efficient load-balancing through distributed token dropping

    Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. Efficient load-balancing through distributed token dropping. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures , SPAA '21, page 129–139, New York, NY, USA, 2021. Association for Computing Machinery

    work page 2021

Show all 42 references
  1. [9]

    Programming parallel algorithms

    Guy E Blelloch. Programming parallel algorithms. Communications of the ACM , 39(3):85--97, 1996

    1996

  2. [10]

    The parallel evaluation of general arithmetic expressions

    Richard P Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM (JACM) , 21(2):201--206, 1974

    1974

  3. [11]

    Adaptive out-orientations with applications

    Chandra Chekuri, Aleksander Bj rn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3062--3...

    2024

  4. [12]

    Relevance of temporal cores for epidemic spread in temporal networks

    Martino Ciaperoni, Edoardo Galimberti, Francesco Bonchi, Ciro Cattuto, Francesco Gullo, and Alain Barrat. Relevance of temporal cores for epidemic spread in temporal networks. Scientific reports , 10(1):12529, 2020

    2020

  5. [13]

    Improved dynamic colouring of sparse graphs

    Aleksander Bj rn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1201--1214, 2023

    2023

  6. [14]

    Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

    Richard Cole and Uzi Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 206--219, 1986

    1986

  7. [15]

    Finding the best k in core decomposition: A time and space optimal solution

    Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. Finding the best k in core decomposition: A time and space optimal solution. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) , pages 685--696. IEEE, 2020

    2020

  8. [16]

    Julienne: A framework for parallel graph algorithms using work-efficient bucketing

    Laxman Dhulipala, Guy Blelloch, and Julian Shun. Julienne: A framework for parallel graph algorithms using work-efficient bucketing. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures , pages 293--304, 2017

    2017

  9. [17]

    Theoretically efficient parallel graph algorithms can be fast and scalable

    Laxman Dhulipala, Guy E Blelloch, and Julian Shun. Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing (TOPC) , 8(1):1--70, 2021

    2021

  10. [18]

    Parallel batch-dynamic k-clique counting

    Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. Parallel batch-dynamic k-clique counting. In Symposium on Algorithmic Principles of Computer Systems (APOCS) , pages 129--143. SIAM, 2021

    2021

  11. [19]

    Parallel and streaming algorithms for k-core decomposition

    Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. Parallel and streaming algorithms for k-core decomposition. In international conference on machine learning , pages 1397--1406. PMLR, 2018

    2018

  12. [20]

    Efficient computation of probabilistic core decomposition at web-scale

    Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. Efficient computation of probabilistic core decomposition at web-scale. In 22nd International Conference on Extending Database Technology, EDBT 2019 , pages 325--336. OpenProceedings. org, 2019

    2019

  13. [21]

    Nearly work-efficient parallel dfs in undirected graphs

    Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu. Nearly work-efficient parallel dfs in undirected graphs. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures , pages 273--283, 2023

    2023

  14. [22]

    Improved parallel algorithms for density-based network clustering

    Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi \'c . Improved parallel algorithms for density-based network clustering. In International Conference on Machine Learning , pages 2201--2210. PMLR, 2019

    2019

  15. [23]

    Towards a theory of nearly constant time parallel algorithms

    Joseph Gil, Yossi Matias, and Uzi Vishkin. Towards a theory of nearly constant time parallel algorithms. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science , pages 698--710. IEEE Computer Society, 1991

    1991

  16. [24]

    Parallel dynamic maximal matching

    Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages 427--437, 2024

    2024

  17. [25]

    Explicit and implicit dynamic coloring of graphs with bounded arboricity

    Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic coloring of graphs with bounded arboricity. arXiv preprint arXiv:2002.10142 , 2020

    2002 arXiv

  18. [26]

    Parallel small vertex connectivity in near-linear work and polylogarithmic depth

    Yonggang Jiang and Changki Yun. Parallel small vertex connectivity in near-linear work and polylogarithmic depth. arXiv preprint arXiv:2504.06033 , 2025

    2025 arXiv

  19. [27]

    K-core decomposition of large networks on a single pc

    Wissam Khaouid, Marina Barsky, Venkatesh Srinivasan, and Alex Thomo. K-core decomposition of large networks on a single pc. Proceedings of the VLDB Endowment , 9(1):13--23, 2015

    2015

  20. [28]

    Identification of influential spreaders in complex networks

    Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hern \'a n A Makse. Identification of influential spreaders in complex networks. Nature physics , 6(11):888--893, 2010

    2010

  21. [29]

    Orienting fully dynamic graphs with worst-case time bounds

    Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II 41 , pag...

    2014

  22. [30]

    Parallel k-core decomposition on multicore platforms

    Humayun Kabir and Kamesh Madduri. Parallel k-core decomposition on multicore platforms. In 2017 IEEE international parallel and distributed processing symposium workshops (IPDPSW) , pages 1482--1491. IEEE, 2017

    2017

  23. [31]

    Locality in distributed graph algorithms

    Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing , 21(1):193--201, 1992

    1992

  24. [32]

    Parallel batch-dynamic algorithms for k-core decomposition and related graph problems

    Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , pages 191--204, 2022

    2022

  25. [33]

    Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun

    Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , SPAA '22, page 191–204,...

    2022

  26. [34]

    Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition

    Ying Liu, Ming Tang, Tao Zhou, and Younghae Do. Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition. Scientific reports , 5(1):9602, 2015

    2015

  27. [35]

    Efficient progressive minimum k-core search

    Conggai Li, Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Efficient progressive minimum k-core search. Proceedings of the VLDB Endowment , 2020

    2020

  28. [36]

    A game theoretic approach for k-core minimization

    Sourav Medya, Tianyi Ma, Arlei Silva, and Ambuj Singh. A game theoretic approach for k-core minimization. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems , 2020

    2020

  29. [37]

    Locating influential nodes in complex networks

    Fragkiskos D Malliaros, Maria-Evgenia G Rossi, and Michalis Vazirgiannis. Locating influential nodes in complex networks. Scientific reports , 6(1):19307, 2016

    2016

  30. [38]

    Decomposition of finite graphs into forests

    C St JA Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society , 1(1):12--12, 1964

    1964

  31. [39]

    Parallel algorithms for red–black trees

    Heejin Park and Kunsoo Park. Parallel algorithms for red–black trees. Theoretical Computer Science , 262(1):415--435, 2001

    2001

  32. [40]

    Fully dynamic approximate k-core decomposition in hypergraphs

    Bintao Sun, T-H Hubert Chan, and Mauro Sozio. Fully dynamic approximate k-core decomposition in hypergraphs. ACM Transactions on Knowledge Discovery from Data (TKDD) , 14(4):1--21, 2020

    2020

  33. [41]

    Near-optimal fully dynamic densest subgraph

    Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 181--193, 2020

    2020

  34. [42]

    Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering

    Tom Tseng, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , pages 233--245, 2022

    2022

Pith tools

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