Pith. sign in

REVIEW 3 major objections 5 minor 51 references

Efficient Kernelization Algorithm for Bipartite Graph Matching

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper claims MVM is the first Karp-Sipser kernelization with near-linear worst-case time on CSR-style array storage.

desk verdict The MVM kernelization is a genuinely useful practical contribution with credible speedups, but the headline O(m log n) worst-case bound rests on an unproven and non-obvious halving inequality, so the theory needs major revision. read the letter →

arxiv 2412.00704 v1 pith:HMP2HJFD submitted 2024-12-01 cs.DS

Guang Wu , Xinbiao Gan , Zhengbin Pang , Bo Huang , Bopin Ran This is my paper · ORCID
classification cs.DS MSC 05C7068Q2568R10
keywords bipartitegraphmatchingmaximumkernelizationKarp-Sipserreductionrulesdatanear-lineartimeCSRstorage
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 proposes MVM, an algorithm that applies Karp and Sipser's two data-reduction rules to shrink a bipartite graph before a maximum matching is computed on the kernel. The central claim is that MVM runs in $O(\min(m \log n, n^2))$ time even when the graph is stored in a CSR-like array structure whose per-operation search cost is $O(n)$ in the worst case, a setting where previous Karp-Sipser implementations had an $O(n^2)$ bound. If the claim holds, MVM is the first Karp-Sipser kernelization that is both provably near-linear on sequential, cache-friendly storage and competitive with hash-table or tree-based variants in practice. The paper also reports speedups of 25$\times$ and 56$\times$ over those theoretical hash- and tree-based variants on real graphs, with kernelization reducing the input by orders of magnitude on difficult instances.

What carries the argument

The carrying object is the pair $(\hat{V}, \tilde{V})$: the current set of mergeable vertices and their neighboring boundary vertices. Multi-vertex merging expands $\hat{V}$ until no vertex satisfies $|\Gamma(v) - \tilde{V}| \le 1$, and the merge operation reconnects the whole boundary set to one retained vertex. The key identity for the runtime bound is $N(\hat{V}_r) \le N(\hat{V}_{r-1})/2$, where $N(\hat{V}_r)$ counts merge operations in round $r$; along with $O(m)$ work per round it yields $O(m \log n)$. The storage machinery is a CSR variant in which edge tables are linked by vtx_link_next and vtx_link_last pointers and updates to external vertices are batched and deferred, giving amortized $O(1)$ edge insertions.

What would settle it

Run MVM on the paper's synthetic worst-case graphs with $n = 2^{15}$ through $2^{22}$, counting the number of multi-vertex merge operations performed in each round. If any round contains more than half the previous round's merges, repeatedly, then the halving property used for the bound is false and the claimed $O(m \log n)$ time does not follow from the given proof.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that Karp-Sipser kernelization can be made round-based rather than vertex-by-vertex. In each round, MVM takes an explicit degree-2 vertex, expands to the set $\hat{V}$ of all mergeable vertices that share boundary vertices, and merges the entire boundary set $\tilde{V}$ at once; implicit mergeable vertices are found by the rule that $|\Gamma(v)-\tilde{V}|=1$, and the search itself only touches edges incident to boundary vertices. A balanced processing strategy delays newly created degree-2 vertices to later rounds so that boundary sets in one round do not overlap on the same side of the bipartition. The paper claims this forces the number of multi-vertex merges to at least halve each round, giving $O(\log n)$ rounds and hence $O(m \log n)$ total work on a CSR-like data structure; the same analysis gives an $O(n^2)$ amortized bound, hence $O(\min(m \log n, n^2))$.

Load-bearing premise

The near-linear bound stands on the claim that each round at least halves the number of merge operations, and the paper states this halving without proving it from the preceding round relation. If the halving can fail, the number of rounds could grow with the graph size and the bound would degrade to $O(mn)$.

Editorial extensions

If this is right

  • Kernelization can be inserted as a preprocessing step with a worst-case guarantee on ordinary CSR graphs, so exact maximum matching becomes faster without losing a provable bound on sparse inputs.
  • Because the kernel is smaller and denser, exact algorithms such as PFP solve it more quickly; on com-LiveJournal the paper reports roughly a 230-fold overall speedup.
  • MVM can be combined with maximal matching algorithms on the kernel graph to gain further speed, an option the paper notes but did not include in its fairness comparisons.
  • The amortized $O(1)$ batch update scheme means edge-table updates need not reallocate arrays per insertion, which matters for any subsequent graph algorithm that runs on the kernel.
  • Hash-table and tree-based storage are no longer needed to reach poly-logarithmic bounds, since the claimed $O(m \log n)$ result holds on CSR-like arrays with $O(n)$ search efficiency.

Reading between the lines

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

  • Inference: the proof's load-bearing point is the halving bound $N(\hat{V}_r) \le N(\hat{V}_{r-1})/2$; if that inequality cannot be derived, the worst-case bound would revert to $O(mn)$, so a direct proof or a counterexample would settle the paper's central claim.
  • Inference: the same round-based expansion machinery may transfer to other degree-based preprocessing such as weighted matching or maximum matching in general graphs, because the merge operation is defined locally on degree-2 vertices.
  • Inference: a hybrid that applies balanced rounds only when high-degree boundary vertices are present could recover the small constant-factor losses the paper observes on real-life graphs while preserving the worst-case guarantee.
  • Inference: the deferred batch-update data structure likely transfers to streaming or dynamic graph settings, where postponing cleanup of deleted vertices can reduce update costs below per-edge reallocation.
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

3 major / 5 minor

Summary. The paper proposes MVM, a kernelization algorithm for exact maximum bipartite matching that implements the two Karp-Sipser reduction rules on a CSR-like storage format. It introduces three optimizations: multi-vertex merging, indirect set operations, and a balanced round-based processing order, and claims that the resulting algorithm runs in O(min(m log n, n^2)) even when neighborhood search has O(n) worst-case cost. The paper also designs a linked edge-table data structure for lower-cost vertex merging and reports experiments on 26 real-world and 8 synthetic graphs, showing large speedups over KaSi variants and stable acceleration over maximal-matching initializers.

Significance. The claimed worst-case bound is the main contribution: existing CSR-based implementations of Karp-Sipser kernelization have O(n^2) upper bounds, and a near-linear bound on a storage format with O(n) search would be a genuinely useful robustness guarantee. The engineering ideas are clearly described and the experimental evaluation is extensive, including an ablation of the three strategies and memory measurements. If the proof can be completed, the result is significant; as written, however, the proof of the main theorem is incomplete at the point where the number of rounds is bounded, so the headline theoretical result is not yet established.

major comments (3)
  1. [Section IV-E, Eq. (5)] The analysis reduces to bounding the number R of processing rounds. Eq. (5) asserts N(V_r) <= N(V_{r-1})/2, and the text says this 'can be derived' from Eq. (4), but no derivation is shown. Eq. (4) is a local statement about a single starting vertex in round r whose two neighbors lie in two round-(r-1) boundary sets; it does not imply a global halving of the number of multi-vertex merging operations. It also silently assumes that every vertex that becomes degree-2 in round r has both neighbors arising from previous-round merge sets, which is not argued. If Eq. (5) fails, R can be as large as Theta(n) and the claimed O(m log n) bound degrades to O(mn). A complete proof of the halving property is required before the central claim is supported.
  2. [Section IV-E, Eq. (3)] The equality T_MVM = O(R * m) in Eq. (3) relies on the sentence 'in each iteration, the mergeable vertices on the same side of the bipartite graph have non-overlapping boundary vertices.' This disjointness property is not proved from Algorithm 2; it is exactly what is needed to replace the sum of boundary-vertex degrees by O(m) per round. Since the balanced-processing strategy is one of the three core optimizations, this invariant should be stated and proved explicitly.
  3. [Section V-B, Eq. (6)] The amortized O(1) bound for updating external vertices requires the total gap size y to be Theta(deg(v)). The paper acknowledges that the practical implementation does not enforce this condition unless the edge tables are enlarged, e.g., by doubling. The theoretical complexity statement should therefore include this storage-size assumption explicitly, and the experimental section should state whether the tested implementation relied on the gap condition or on a different mechanism.
minor comments (5)
  1. [Table II] The header misspells 'DATASET' as 'DATESET'.
  2. [Sections I and VI-A] The reference for the KaSi comp baseline is inconsistent: Section I cites [33] while Section VI-A cites [37]; please unify.
  3. [Section IV-E, Eq. (5)] The symbol N(.) is used without a precise definition; please define it as the number of multi-vertex merging operations performed in a given round.
  4. [Algorithm 2, lines 15-19] The early-exit condition uses |V~| = |V^|, but the case |V~| > |V^| can arise when a newly added mergeable vertex contributes a boundary vertex not previously present; this case is not discussed.
  5. [Section VI] The paper says each instance was run five times and averaged, but the algorithms are deterministic; this is not an error, but a brief explanation of what varies across runs would help the reader interpret the reported times.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the core derivation is self-contained, and the unsupported halving inequality in Eq. (5) is a proof gap, not a circular reduction.

full rationale

The paper does not contain a load-bearing circular step. The Karp-Sipser reduction rules are imported as an external theorem from Karp and Sipser's work, and the algorithm's correctness depends on those external rules plus the matching tree recorded during execution, not on any quantity defined in terms of the claimed result. The time-complexity analysis in Section IV-E uses only graph parameters n and m, the algorithm's round structure, and the asserted halving inequality N(V_r) <= N(V_{r-1})/2; no fitted constant, no empirical parameter, and no data-derived prediction is renamed as a theoretical result. The unsupported nature of Eq. (5) is a genuine proof gap that threatens the O(m log n) claim, but it is not circularity: the inequality is not assumed as an input, not defined to make the conclusion true, and not justified by a self-citation. The two self-citations, GraphCube [26] and MatchBG [34], are contextual or comparative baselines and do not carry the proof. Therefore, under the hard rule that circularity requires a specific reduction by definition, fit, or self-citation chain, the honest finding is no significant circularity with score 0.

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

The algorithm has no fitted parameters. The central theoretical claim rests on three unproven structural lemmas about the round structure of the algorithm and one data-structure assumption; none of these are externally benchmarked or machine-checked.

assumptions (4)
  • domain assumption The Karp-Sipser data reduction rules produce a kernel from which a maximum matching of the original graph can be reconstructed in linear time.
    The paper relies on the correctness of Rules 1 and 2 from Karp and Sipser (1981), cited as [22], and on the reconstruction procedure via the matching tree T in Section IV-D.
  • ad hoc to paper In each processing round, the boundary vertex sets of different multi-vertex merging operations on the same side of the bipartition are disjoint.
    This assumption is used in Eq. (3) to claim per-round cost O(m). It is asserted in Section IV-E but not proven; adjacency of mergeable vertices is defined via shared boundary vertices, which does not by itself guarantee global disjointness across all groups in a round.
  • ad hoc to paper The number of multi-vertex merging operations halves each round: N(V_r) <= N(V_{r-1})/2.
    This inequality, Eq. (5), is used to derive R = O(log n). The paper's justification from Eq. (4) is not a complete proof, and this is the load-bearing assumption for the O(m log n) bound.
  • ad hoc to paper The amortized O(1) cost per edge insertion in the external-vertex update requires gap size y = Θ(deg(v)) in edge tables.
    The paper states that this is achieved by doubling the edge table size, but the measured implementation does not double, so the practical algorithm does not strictly enjoy the guaranteed amortized bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Kernelization Algorithm for Bipartite Graph Matching." pith.science (2026). https://pith.science/paper/HMP2HJFD

@misc{pith2026241200704,
  author       = {Pith},
  title        = {Pith review of: Efficient Kernelization Algorithm for Bipartite Graph Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HMP2HJFD}},
  note         = {Machine review of arXiv:2412.00704}
}
read the original abstract

Finding the maximum matching in bipartite graphs is a fundamental graph operation widely used in various fields. To expedite the acquisition of the maximum matching, Karp and Sipser introduced two data reduction rules aimed at decreasing the input size. However, the KaSi algorithm, which implements the two data reduction rules, has several drawbacks: a high upper bound on time complexity and inefficient storage structure. The poor upper bound on time complexity makes the algorithm lack robustness when dealing with extreme cases, and the inefficient storage structure struggles to balance vertex merging and neighborhood traversal operations, leading to poor performance on real-life graphs. To address these issues, we introduced MVM, an algorithm incorporating three novel optimization strategies to implement the data reduction rules. Our theoretical analysis proves that the MVM algorithm, even when using data structures with the worst search efficiency, can still maintain near-linear time complexity, ensuring the algorithm's robustness. Additionally, we designed an innovative storage format that supports efficient vertex merging operations while preserving the locality of edge sets, thus ensuring the efficiency of neighborhood traversals in graph algorithms. Finally, we conduct evaluations on both real-life and synthetic graphs. Extensive experiments demonstrate the superiority of our method.

Figures

Figures reproduced from arXiv: 2412.00704 by the authors.

Figure 1
Figure 1. An example of Karp and Sipser’s data reduction rule, where the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. An example of updating the edge tables for external vertices, [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. The runtime of MVM with different optimization strategies. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figures from the paper (4 more)
Figure 5
Figure 5. Figure 5: The runtime of MVM and the variants of KaSi algorithm. [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 9
Figure 9. Figure 9: The overall runtime for obtaining the maximum matching on real-life [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 8
Figure 8. Figure 8: The runtime on the worst-case instances. [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 11
Figure 11. Figure 11: The kernelization quality on real-life graphs. [PITH_FULL_IMAGE:figures/full_fig_p010_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 49 canonical work pages

  1. [1]

    Controllability of complex networks,

    Y .-Y . Liu, J.-J. E. Slotine, and A.-L. Barab ´asi, “Controllability of complex networks,” Nature, vol. 473, pp. 167–173, 2011

    work page 2011

  2. [2]

    Minimal control nodes for strong structural observability of discrete-time iterative systems: Explicit formulas and polynomial-time algorithms,

    S. Zhu, J. Lu, D. W. C. Ho, and J. Cao, “Minimal control nodes for strong structural observability of discrete-time iterative systems: Explicit formulas and polynomial-time algorithms,” IEEE Transactions on Automatic Control , vol. 69, pp. 2158–2173, 2024

    work page 2024

  3. [3]

    Addressing the minimum fleet problem in on-demand urban mobility,

    M. M. Vazifeh, P. Santi, G. Resta, S. H. Strogatz, and C. Ratti, “Addressing the minimum fleet problem in on-demand urban mobility,” Nature, vol. 557, pp. 534–538, 2018

    work page 2018

  4. [4]

    Strategic resource selection with homophilic agents,

    J. G. Harder, S. Krogmann, P. Lenzner, and A. Skopalik, “Strategic resource selection with homophilic agents,” in IJCAI, 2023

    work page 2023

  5. [5]

    The multi-agent transportation problem,

    P. Bachor, R.-D. Bergdoll, and B. Nebel, “The multi-agent transportation problem,” in AAAI Conference on Artificial Intelligence , 2023

    work page 2023

  6. [6]

    Ive: Accelerating enumeration-based subgraph matching via exploring isolated vertices,

    Z. Jiang, S. Zhang, X. Hou, M. Yuan, and H. You, “Ive: Accelerating enumeration-based subgraph matching via exploring isolated vertices,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 4208–4221, 2024

    work page 2024

  7. [7]

    Bice: Exploring compact search space by using bipartite matching and cell-wide verification,

    Y . Choi, K. Park, and H. Kim, “Bice: Exploring compact search space by using bipartite matching and cell-wide verification,” Proc. VLDB Endow., vol. 16, pp. 2186–2198, 2023

    work page 2023

  8. [8]

    Efficient and scalable labeled subgraph matching using sgmatch,

    C. R. Rivero and H. M. Jamil, “Efficient and scalable labeled subgraph matching using sgmatch,” Knowledge and Information Systems , vol. 51, pp. 61–87, 2017

    work page 2017

Show all 51 references
  1. [9]

    Dilation choice sets, dul- mage–mendelsohn decomposition, and structural controllability,

    C. Commault and J. van der Woude, “Dilation choice sets, dul- mage–mendelsohn decomposition, and structural controllability,” IEEE Transactions on Control of Network Systems , vol. 11, pp. 1046–1055, 2024

    2024

  2. [10]

    A survey of direct methods for sparse linear systems,

    T. A. Davis, S. Rajamanickam, and W. M. Sid-Lakhdar, “A survey of direct methods for sparse linear systems,” Acta Numerica , vol. 25, pp. 383 – 566, 2016

    2016

  3. [11]

    Computing the block triangular form of a sparse matrix,

    A. Pothen and C.-J. Fan, “Computing the block triangular form of a sparse matrix,” ACM Trans. Math. Softw. , vol. 16, pp. 303–324, 1990

    1990

  4. [12]

    Efficient cross dynamic task assignment in spatial crowdsourcing,

    T. Ren, X. Zhou, K. Li, Y . Gao, J. Zhang, and K. Li, “Efficient cross dynamic task assignment in spatial crowdsourcing,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE) , pp. 1420–1432, 2023

    2023

  5. [13]

    Loyalty-based task assignment in spatial crowdsourcing,

    T. H. M. Lai, Y . Zhao, W. Qian, and K. Zheng, “Loyalty-based task assignment in spatial crowdsourcing,” Proceedings of the 31st ACM International Conference on Information & Knowledge Management , 2022

    2022

  6. [14]

    Real-time cross online matching in spatial crowdsourcing,

    Y . Cheng, B. Li, X. Zhou, Y . Yuan, G. Wang, and L. Chen, “Real-time cross online matching in spatial crowdsourcing,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE) , pp. 1–12, 2020

    2020

  7. [15]

    Dynamic pricing in spatial crowdsourcing: A matching-based approach,

    Y . Tong, L. Wang, Z. Zhou, L. Chen, B. Du, and J. Ye, “Dynamic pricing in spatial crowdsourcing: A matching-based approach,” in Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, (New York, NY , USA), p. 773–788, Association for Computing Mach...

    2018

  8. [16]

    Design, implementation, and analysis of maximum transversal algorithms,

    I. S. Duff, K. Kaya, and B. Uc ¸ar, “Design, implementation, and analysis of maximum transversal algorithms,” ACM Transactions on Mathematical Software (TOMS) , vol. 38, pp. 1 – 31, 2011

    2011

  9. [17]

    Karp-sipser based kernels for bipartite graph matching,

    K. Kaya, J. Langguth, I. Panagiotas, and B. Uc ¸ar, “Karp-sipser based kernels for bipartite graph matching,” in Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020 , pp. 134– 145, SIAM, 2020

    2020

  10. [18]

    Engineering Fast Almost Optimal Al- gorithms for Bipartite Graph Matching,

    I. Panagiotas and B. Uc ¸ar, “Engineering Fast Almost Optimal Al- gorithms for Bipartite Graph Matching,” in 28th Annual European Symposium on Algorithms (ESA 2020) , vol. 173, pp. 76:1–76:23, 2020

    2020

  11. [19]

    F. N. Abu-Khzam, S. Lamm, M. Mnich, A. Noe, C. Schulz, and D. Strash, Recent Advances in Practical Data Reduction , pp. 97–133. Cham: Springer Nature Switzerland, 2022

    2022

  12. [20]

    Approximation algorithms in combinatorial scientific computing,

    A. Pothen, S. M. Ferdous, and F. Manne, “Approximation algorithms in combinatorial scientific computing,” Acta Numerica, vol. 28, pp. 541 – 633, 2019

    2019

  13. [21]

    Fast parameterized preprocessing for polynomial-time solvable graph problems,

    A.-S. Himmel, G. B. Mertzios, A. Nichterlein, and R. Niedermeier, “Fast parameterized preprocessing for polynomial-time solvable graph problems,” Communications of the ACM , vol. 67, pp. 70 – 79, 2024

    2024

  14. [22]

    Maximum matching in sparse random graphs,

    R. M. Karp and M. Sipser, “Maximum matching in sparse random graphs,” 22nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 364–375, 1981

    1981

  15. [23]

    Brandst ¨adt, V

    A. Brandst ¨adt, V . B. Le, and J. P. Spinrad, Graph classes: a survey . SIAM, 1999

    1999

  16. [24]

    Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency,

    J. Chhugani, N. Satish, C. Kim, J. Sewall, and P. Dubey, “Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency,” in 2012 IEEE 26th International Parallel and Distributed Processing Symposium, pp. 378–389, IEEE, 2012

    2012

  17. [25]

    Graphscope: a unified engine for big graph processing,

    W. Fan, T. He, L. Lai, X. Li, Y . Li, Z. Li, Z. Qian, C. Tian, L. Wang, J. Xu, et al., “Graphscope: a unified engine for big graph processing,” Proceedings of the VLDB Endowment , vol. 14, no. 12, pp. 2879–2892, 2021

    2021

  18. [26]

    Graphcube: Interconnection hierarchy-aware graph pro- cessing,

    X. Gan, G. Wu, S. Qiu, F. Xiong, J. Si, J. Fang, D. Dong, C. Gong, T. Li, and Z. Wang, “Graphcube: Interconnection hierarchy-aware graph pro- cessing,” in Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming , PPoPP ’24, (New ...

    2024

  19. [27]

    Dgap: Efficient dynamic graph analysis on persistent memory,

    A. A. R. Islam and D. Dai, “Dgap: Efficient dynamic graph analysis on persistent memory,” SC23: International Conference for High Perfor- mance Computing, Networking, Storage and Analysis , pp. 1–14, 2023

    2023

  20. [28]

    A parallel packed memory array to store dynamic graphs,

    B. Wheatman and H. Xu, “A parallel packed memory array to store dynamic graphs,” in Workshop on Algorithm Engineering and Experi- mentation, 2021

    2021

  21. [29]

    Packed memory arrays - rewired,

    D. D. Leo and P. A. Boncz, “Packed memory arrays - rewired,” 2019 IEEE 35th International Conference on Data Engineering (ICDE) , pp. 830–841, 2019

    2019

  22. [30]

    Exploiting fine-grained redundancy in set-centric graph pattern mining,

    Z. Lin, K. Meng, C. Shui, K. Zhang, J. Xiao, and G. Tan, “Exploiting fine-grained redundancy in set-centric graph pattern mining,” in Pro- ceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming , PPoPP ’24, (New York, NY , USA), p....

    2024

  23. [31]

    Cyclosa: Redundancy-free graph pattern mining via set dataflow,

    C. Gui, X. Liao, L. Zheng, and H. Jin, “Cyclosa: Redundancy-free graph pattern mining via set dataflow,” in Proceedings of the 2023 USENIX Annual Technical Conference, USENIX ATC 2023, Boston, MA, USA, July 10-12, 2023 (J. Lawall and D. Williams, eds.), pp. 71–85, USENIX Assoc...

    2023

  24. [32]

    D. B. West et al. , Introduction to graph theory , vol. 2. Prentice hall Upper Saddle River, 2001

    2001

  25. [33]

    Data reduction for maximum matching on real-world graphs: Theory and experiments,

    T. Koana, V . Korenwein, A. Nichterlein, R. Niedermeier, and P. Zschoche, “Data reduction for maximum matching on real-world graphs: Theory and experiments,” ACM J. Exp. Algorithmics , vol. 26, Apr. 2021

    2021

  26. [34]

    Matchbg: A boundary subgraph-based maximal matching algorithm for bipartite graphs,

    G. Wu and X. Gan, “Matchbg: A boundary subgraph-based maximal matching algorithm for bipartite graphs,” in Database Systems for Advanced Applications: 29th International Conference, DASFAA 2024, Gifu, Japan, July 2–5, 2024, Proceedings, Part IV , (Berlin, Heidelberg), p. 463–4...

    2024

  27. [35]

    The university of florida sparse matrix collection,

    T. A. Davis and Y . Hu, “The university of florida sparse matrix collection,” ACM Trans. Math. Softw. , vol. 38, pp. 1:1–1:25, 2011

    2011

  28. [36]

    SNAP Datasets: Stanford large network dataset collection

    J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection.” http://snap.stanford.edu/data, June 2014

    2014

  29. [37]

    Shared-memory implementa- tion of the karp-sipser kernelization process,

    J. Langguth, I. Panagiotas, and B. Uc ¸ar, “Shared-memory implementa- tion of the karp-sipser kernelization process,” 2021 IEEE 28th Interna- tional Conference on High Performance Computing, Data, and Analytics (HiPC), pp. 71–80, 2021

    2021

  30. [38]

    Heuristic initialization for bipartite matching problems,

    J. Langguth, F. Manne, and P. Sanders, “Heuristic initialization for bipartite matching problems,” ACM J. Exp. Algorithmics , vol. 15, 2010

    2010

  31. [39]

    Distributed-memory algorithms for maximum cardinality matching in bipartite graphs,

    A. Azad and A. Buluc ¸, “Distributed-memory algorithms for maximum cardinality matching in bipartite graphs,” 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , pp. 32–42, 2016

    2016

  32. [40]

    Graphs over time: densification laws, shrinking diameters and possible explanations,

    J. Leskovec, J. M. Kleinberg, and C. Faloutsos, “Graphs over time: densification laws, shrinking diameters and possible explanations,” in Knowledge Discovery and Data Mining , 2005

    2005

  33. [41]

    Defining and evaluating network communities based on ground-truth,

    J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” Knowledge and Information Systems , vol. 42, pp. 181 – 213, 2012

    2012

  34. [42]

    The webgraph framework i: compression techniques,

    P. Boldi and S. Vigna, “The webgraph framework i: compression techniques,” in The Web Conference, 2004

    2004

  35. [43]

    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,” ArXiv, vol. abs/1011.5425, 2010

    2010 arXiv

  36. [44]

    Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,

    J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics, vol. 6, pp. 123 – 29, 2008. 11

    2008

  37. [45]

    Group formation in large social networks: membership, growth, and evolution,

    L. Backstrom, D. P. Huttenlocher, J. M. Kleinberg, and X. Lan, “Group formation in large social networks: membership, growth, and evolution,” in Knowledge Discovery and Data Mining , 2006

    2006

  38. [46]

    Data analysis in public social networks,

    L. Takac, “Data analysis in public social networks,” 2012

    2012

  39. [47]

    Signed networks in social media,

    J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg, “Signed networks in social media,” Proceedings of the SIGCHI Conference on Human Factors in Computing Systems , 2010

    2010

  40. [48]

    Predict- ing positive and negative links in online social networks,

    J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg, “Predict- ing positive and negative links in online social networks,” ArXiv, vol. abs/1003.2429, 2010

    2010 arXiv

  41. [49]

    Local higher-order graph clustering,

    H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, “Local higher-order graph clustering,” Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , 2017

    2017

  42. [50]

    Using triangles to improve community detection in directed networks,

    C. Klymko, D. F. Gleich, and T. G. Kolda, “Using triangles to improve community detection in directed networks,” ArXiv, vol. abs/1404.5874, 2014

    2014 arXiv

  43. [51]

    Randomized greedy algorithms for the maximum matching problem with new analysis,

    M. Poloczek and M. Szegedy, “Randomized greedy algorithms for the maximum matching problem with new analysis,” 2012 IEEE 53rd An- nual Symposium on Foundations of Computer Science (FOCS), pp. 708– 717, 2012. 12

    2012

Pith tools

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