Pith. sign in

REVIEW 3 major objections 3 minor 49 references

Parallel local-max computes 1/d-approximate hypergraph matchings in O(log m) time, with near-linear work.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review

2026-08-02 20:30 UTC pith:5YTOZ6CH

load-bearing objection Solid GPU engineering and credible CREW bounds, but the headline CRCW theorem has a load-bearing work-bound gap that needs fixing before this is publishable as claimed. the 3 major comments →

arxiv 2602.22976 v3 pith:5YTOZ6CH submitted 2026-02-26 cs.DS

Efficient Parallel Algorithms for Hypergraph Matching

Henrik Reinst\"adtler , Christian Schulz , Nodari Sitchinava , Fabian Walliser This is my paper
classification cs.DS MSC 68W1068W2005C65
keywords hypergraph matchingparallel algorithmsPRAMGPUmaximal matchingapproximation algorithmlocal maxline graph
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper tries to establish that the classical greedy local-maximum strategy for hypergraph matching—repeatedly picking edges heavier than all their neighbors—can be turned into an efficient parallel algorithm. The authors prove that a parallel version runs in O(log m) time with O(κ log m) work on the CRCW PRAM (a concurrent-read concurrent-write parallel random-access machine), and give CREW variants including a work-optimal one, all with a 1/d approximation ratio for hypergraphs of maximum edge size d. They also implement the approach on a GPU and report speedups of up to 76× over a single-core CPU greedy. If the theoretical bounds hold, this gives a practical parallel implementation with such guarantees for hypergraph matching. The central mechanism is choosing locally maximal edges in parallel and deleting their neighborhoods, reducing the problem to a parallel maximal independent set computation on the line graph.

Core claim

The central claim is that repeatedly identifying edges that are heavier than all their neighbors, in parallel, produces a maximal matching of weight at least 1/d of the optimum after O(log m) rounds with high probability. In each round, every vertex votes for its heaviest incident edge; an edge is added to the matching if all its vertices vote for it, and then all edges sharing a vertex with it are soft-deleted. Randomly perturbed weights make ties unlikely and guarantee a geometric decrease in the number of active edges. On the CRCW PRAM (concurrent-read concurrent-write parallel random-access machine), this takes O(log m) time and O(κ log m) work; the CREW variant uses prefix-sum reduction

What carries the argument

The 'locally maximal edge' rule with random per-round weights. Every vertex selects its heaviest incident edge; those edges chosen by all their vertices are matched and their neighborhoods are deactivated. The key identity is that this process is exactly the parallel maximal independent set algorithm on the line graph of the hypergraph—the graph whose vertices are the hyperedges and whose edges connect hyperedges that share a vertex—so the line graph has m vertices and the standard MIS analysis bounds the number of rounds to O(log m) with high probability. The work-optimal version additionally uses parallel prefix-sum compaction to rebuild the hypergraph after each round so that work is prop

Load-bearing premise

The claim that each round costs only O(κ) work assumes that a vertex's heaviest incident edge can be identified with total work proportional to the number of incident edges; the explicit construction instead uses n·Δ² processors, which can be vastly larger than κ.

What would settle it

Take a hypergraph with one vertex shared by all edges and each edge of size 2 (so n ≈ Δ and κ ≈ 2n), implement the described CRCW arg-max construction, and measure the per-round work; if it scales as nΔ² rather than κ, the O(κ log m) bound is violated.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • A 1/d-approximate maximal matching in hypergraphs can be computed in logarithmic parallel time with near-linear work, preserving the sequential greedy guarantee while exposing massive parallelism.
  • The CREW and work-optimal variants adapt the algorithm to memory models with no concurrent writes and to settings where total work must be optimal, including external-memory and MapReduce-style simulations outlined in the paper.
  • On GPUs, the implementation runs up to 76× faster than a single-core CPU greedy, indicating that the theoretical parallelism is realizable in practice.
  • The approximation bound 1/d is shown tight for the local-max strategy, so any better approximation would require a different algorithmic principle.
  • Because the algorithm reduces to maximal independent set on the line graph, future improvements to parallel MIS algorithms directly translate to hypergraph matching.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper's O(κ log m) work bound for the CRCW algorithm depends on the claim that each vertex can find its heaviest incident edge in O(1) time; the given construction uses n·Δ² processors, which is not O(κ) in general—so this is a point a reader would want to see patched before relying on Theorem 1 as stated.
  • The same local-max template could likely be adapted to compute matchings in k-partite hypergraphs or in the relaxed b-matching problem, where vertices allow multiple matched edges, by changing the vote rule.
  • The GPU results vary noticeably with the random number generator used for tie-breaking; this suggests the practical performance is sensitive to noise quality, and a cheaper or more deterministic tie-break may change speedups.
  • If the round count is truly O(log m) on the line graph, then any hypergraph family whose line graph has bounded degree would enjoy even faster convergence—something the paper does not explore.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper proposes a family of parallel algorithms for computing maximal matchings in hypergraphs. The central theoretical claims are: a Sum-CRCW algorithm with O(log m) time and O(κ log m) work; a CREW variant with O((log Δ + log d) log m) time and O(κ log m) work; a work-optimal CREW variant with O((log m + log n) log m) time and O(κ) work; and a 1/d approximation guarantee. The paper also reports GPU/CUDA/Kokkos implementations with speedups up to 76× over a single-core CPU greedy baseline.

Significance. If the theoretical bounds were correct, this would be a useful contribution: hypergraph matching is NP-hard, and a practical parallel algorithm with PRAM guarantees and a 1/d approximation would be of interest to both theory and systems communities. The experimental study, including the comparison against GPU and multicore baselines, is valuable. However, the headline CRCW work bound is based on an inconsistent accounting of the parallel work and collapses as stated. The CREW variants and the experimental results may be salvageable, but the main theoretical contribution needs substantial rework.

major comments (3)
  1. [Section 4.2, Claim 4.2 (and Theorem 1)] The per-round work accounting is internally inconsistent. The second subphase is described as using n·Δ² PEs, with each vertex computing Δ² pairwise comparisons among its incident edges, followed by a SUM reduction. This performs Θ(nΔ²) operations per round. For a Δ-regular hypergraph, κ = Θ(nΔ), so nΔ² = Δ·κ, which is not O(κ) when Δ = ω(1). The same paragraph nevertheless concludes that the total work is O(κ). Thus Theorem 1's O(κ log m) work bound is unsupported; the described subphase alone would give Θ(nΔ²) work per round. This is not a minor proof gap: the paper supplies no O(Δ)-work, O(1)-time algorithm for exact maximum of Δ weights on a Sum-CRCW, and a star hypergraph with one vertex of degree Δ (κ = Θ(Δ)) isolates exactly this difficulty. The CRCW headline claim cannot stand as stated.
  2. [Abstract vs. Theorem 1] The abstract claims CRCW time O(log log Δ log m), while Theorem 1 and Claim 4.2 state O(log m) time with O(κ log m) work. These are different bounds. If the intended per-round argmax uses an O(log log Δ)-time procedure, then the all-pairs O(1)-time description in Claim 4.2 is not the algorithm being analyzed, and the work bound must be re-evaluated. As written, the reader cannot tell which result is being claimed.
  3. [Lemma 1] The proof of the 1/d approximation guarantee is garbled and does not establish the stated weighted claim. The notation M and M is used inconsistently, and the sentence 'f must not be locally maximal; otherwise, it would be in M' is not a valid proof step for a weighted approximation bound. More importantly, the algorithms randomize edge weights in every round. Selecting local maxima with respect to noisy weights is not the same as selecting local maxima with respect to the original input weights, so the weighted 1/d guarantee is not justified. For cardinality matching, any maximal matching trivially has size at least 1/d of the maximum, but the weighted statement requires a careful argument that is absent.
minor comments (3)
  1. [Theorem 3 proof] The statement that 'work and size decrease geometrically following the proof of number of rounds (Theorem 4.2) using Luby's algorithm' is too terse. Luby's algorithm gives an O(log m) round bound, but the authors should state explicitly how the remaining hypergraph shrinks in a way that justifies the total O(κ) work, rather than O(κ log m). Also, the reference should be to Claim 4.2, not Theorem 4.2.
  2. [Section 5.1 / experiments] The theoretical section says 'small random perturbations' are added to weights, but the experiments use noise uniformly sampled from [0,100]. For weighted instances with small integer weights, this can dominate the original weights and change the objective. Please clarify whether the approximation guarantee applies to this noisy setting or only to cardinality matching.
  3. [Appendix B, Table 1] The column ordering in Table 1 is confusing: the header lists Name, avg |e|, |E|, d, Δ, |V|, but the rows appear to have columns in a different order. Please reformat for readability.

Circularity Check

0 steps flagged

No circularity: the approximation proof is self-contained and the round bound reduces to Luby's external algorithm; the main weakness is a PRAM work accounting error, not a circular step.

full rationale

The central derivation is not circular. Lemma 1 gives a self-contained charging argument for the 1/d approximation using only maximality of the produced matching and the fact that every hyperedge has at most d vertices. The round bound is obtained by an explicit reduction to Luby's MIS algorithm on the line graph, citing the external independent result [33]; the paper does not assume its own theorem to prove itself. The CREW and work-optimal variants are analyzed with standard prefix-sum/OR/MAX reductions in Appendix A, again without reusing the claims being proved. The authors' self-citations ([27], [43], [44]) appear only as related work, experimental baselines, and dataset sources; they are not premises for the new PRAM time/work bounds or approximation guarantee. The notable flaw in the paper is Claim 4.2, where the per-round vertex-max step is said to require O(1) time and O(kappa) work while using n*Delta^2 processors and computing Delta^2 pairwise comparisons per vertex. On standard PRAM accounting this is Theta(n Delta^2) = Theta(Delta*kappa) work, which is not O(kappa) for large Delta. That is a correctness/complexity error, not circularity: no equation reduces to its own input, and no fitted parameter is renamed as a prediction. Therefore the circularity score is 0.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

The central claims rest on standard PRAM assumptions, the line graph reduction, and Luby's round bound. No new physical or mathematical entities are introduced. The only hand-chosen experimental parameter is the random noise interval, which does not affect the theoretical bounds.

free parameters (1)
  • Random noise interval [0,100] = uniform [0,100]
    Hand-chosen in Section 6.1 for experiments; not derived theoretically. The paper notes the Wiki instance requires 16 rounds vs 5-7 on others, suggesting round counts are sensitive to weight distribution.
axioms (4)
  • domain assumption Random number generation takes O(1) time.
    Stated explicitly in Section 2.1 as a common assumption; load-bearing for the O(1)-time-per-round claim since new random weights are drawn every round.
  • standard math Luby's MIS algorithm computes a maximal independent set in O(log n) rounds w.h.p. on any graph.
    Used in Claim 4.2 to bound the number of rounds by O(log m) via the line graph reduction. The paper does not prove this theorem.
  • domain assumption Edge weights in each round are independent and uniformly distributed.
    Section 4.2 states the analysis assumes a uniform distribution of weights for each round independently; required for the w.h.p. round bound.
  • standard math Hyperedge local-max selection is equivalent to vertex local-max selection in the line graph L(H).
    Definition in Section 2.1; used in the reduction to Luby. The line graph has m vertices and edges represent conflicts between hyperedges.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Parallel Algorithms for Hypergraph Matching." pith.science (2026). https://pith.science/paper/5YTOZ6CH

@misc{pith2026260222976,
  author       = {Pith},
  title        = {Pith review of: Efficient Parallel Algorithms for Hypergraph Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YTOZ6CH}},
  note         = {Machine review of arXiv:2602.22976}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We present efficient parallel algorithms for computing maximal matchings in hypergraphs. Our algorithm finds locally maximal edges in the hypergraph and adds them in parallel to the matching. In the CRCW PRAM models our algorithms achieve $O(\log{\log{\Delta}}\log{m})$ time with $O(\kappa\log {m})$ work w.h.p. where $m$ is the number of hyperedges, and $\kappa$ is the sum and $\Delta$ is the maximum of all vertex degrees. The CREW PRAM model algorithm has a running time of $O((\log{\Delta}+\log{d})\log{m})$ and requires $O(\kappa \log {m})$ work w.h.p. It can be implemented work-optimal with $O(\kappa)$ work in $O((\log{m}+\log{n})\log{m})$ time. We prove a~$1/d$-approximation guarantee for our algorithms. We evaluate our algorithms experimentally by implementing and running the proposed algorithms on the GPU using CUDA and Kokkos. Our experimental evaluation demonstrates the practical efficiency of our approach on real-world hypergraph instances, yielding a speed up of up to 76 times compared to a single-core CPU algorithm.

Figures

Figures reproduced from arXiv: 2602.22976 by Christian Schulz, Fabian Walliser, Henrik Reinst\"adtler, Nodari Sitchinava.

Figure 1
Figure 1. Figure 1: Visualization for the proof of the tight lower bound in Lemma 2. There [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Results on hypergraphs. Average speedup over [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Experimental results on graphs. Speedup over [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 21 canonical work pages · 2 internal anchors

  1. [1]

    10.1090/conm/588

    Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Chal- lenge Workshop (2013). 10.1090/conm/588

    doi:10.1090/conm/588 2013

  2. [2]

    Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Commun. ACM (9) (1988). 10.1145/48529.48535

    arXiv 1988

  3. [3]

    10.1007/978-3-642-30397-5_10

    Auer, B.F., Bisseling, R.H.: A gpu algorithm for greedy graph matching (2012). 10.1007/978-3-642-30397-5_10

    work page doi:10.1007/978-3-642-30397-5_10 2012

  4. [4]

    In: SODA 2023

    Balliu, A., Brandt, S., Kuhn, F., Olivetti, D.: Distributed maximal matching and maximal independent set on hypergraphs. In: SODA 2023. SIAM (2023). 10.1137/1.9781611977554.ch100

    work page doi:10.1137/1.9781611977554.ch100 2023

  5. [5]

    Belov, A., Diepold, D., Heule, M., Järvisalo, M.: The SAT competition 2014.http: //www.satcompetition.org/2014/index.shtml(2014)

    2014

  6. [6]

    In: SWAT 2000 (2000)

    Berman, P.: Ad/2 approximation for maximum weight independent set ind-claw free graphs. In: SWAT 2000 (2000). 10.1007/3-540-44985-X_19

    work page doi:10.1007/3-540-44985-x_19 2000

  7. [7]

    Algorith- mica (2017)

    Besser, B., Poloczek, M.: Greedy matching: Guarantees and limitations. Algorith- mica (2017). 10.1007/s00453-015-0062-2

    work page doi:10.1007/s00453-015-0062-2 2017

  8. [8]

    In: Euro-Par 2013 (2013)

    Birn, M., Osipov, V., Sanders, P., Schulz, C., Sitchinava, N.: Efficient parallel and external matching. In: Euro-Par 2013 (2013). 10.1007/978-3-642-40047-6_66

    work page doi:10.1007/978-3-642-40047-6_66 2013

  9. [9]

    Blelloch, G.E., Brady, A.C.: Parallel batch-dynamic maximal matching with con- stant work per update (2025)

    2025

  10. [10]

    ACM Trans

    Burtscher, M., Devale, S., Azimi, S., Jaiganesh, J., Powers, E.: A high-quality and fast maximal independent set implementation for gpus. ACM Trans. Parallel Comput. (2) (2018). 10.1145/3291525

    work page doi:10.1145/3291525 2018

  11. [11]

    In: SODA 1995 (1995)

    Chiang, Y., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: SODA 1995 (1995)

    1995

  12. [12]

    ACM Trans

    Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Trans. on Math. Software (1) (2011). 10.1145/2049662.2049663

    arXiv 2011

  13. [13]

    Communications of the ACM (1) (2008)

    Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Communications of the ACM (1) (2008). 10.1145/1327452.1327492

    arXiv 2008

  14. [14]

    Dhulipala, L., Blelloch, G.E., Shun, J.: Theoretically efficient parallel graph algo- rithms can be fast and scalable (2021) Efficient Parallel Algorithms for Hypergraph Matching 17

    2021

  15. [15]

    10.1016/S0020-0190(02)00393-9

    Drake, D., Hougardy, S.: A Simple Approximation Algorithm for the Weighted Matching Problem (2003). 10.1016/S0020-0190(02)00393-9

    work page doi:10.1016/s0020-0190(02)00393-9 2003

  16. [16]

    In: SEA 2019 (2019)

    Dufossé, F., Kaya, K., Panagiotas, I., Uçar, B.: Effective heuristics for matchings in hypergraphs. In: SEA 2019 (2019). 10.1007/978-3-030-34029-2_17

    work page doi:10.1007/978-3-030-34029-2_17 2019

  17. [17]

    CJM (1965)

    Edmonds, J.: Paths, trees, and flowers. CJM (1965). 10.4153/CJM-1965-045-4

    doi:10.4153/cjm-1965-045-4 1965

  18. [18]

    In: FOCS 1999 (1999)

    Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algo- rithms. In: FOCS 1999 (1999). 10.1109/SFFCS.1999.814600

    arXiv 1999

  19. [19]

    In: RailTokyo2015 (2015)

    Froger, A., Guyon, O., Pinson, E.: A set packing approach for scheduling passenger train drivers: the French experience. In: RailTokyo2015 (2015)

    2015

  20. [20]

    In: Comb

    Fürer, M., Yu, H.: Approximating thek-set packing problem by local improve- ments. In: Comb. Opt. (2014). 10.1007/978-3-319-09174-7_35

    work page doi:10.1007/978-3-319-09174-7_35 2014

  21. [21]

    Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. (2) (1985). 10.1016/0022-0000(85)90014-5

    doi:10.1016/0022-0000(85)90014-5 1985

  22. [22]

    In: ALENEX 2008 (2008)

    Geisberger, R., Sanders, P., Schultes, D.: Better approximation of betweenness centrality. In: ALENEX 2008 (2008). 10.1137/1.9781611972887.9

    work page doi:10.1137/1.9781611972887.9 2008

  23. [23]

    Ghaffari, M., Trygub, A.: Parallel dynamic maximal matching (2024)

    2024

  24. [24]

    10.1007/978-3-642-25591-5_39

    Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the mapreduce framework (2011). 10.1007/978-3-642-25591-5_39

    doi:10.1007/978-3-642-25591-5_39 2011

  25. [25]

    Scalable High-Quality Hypergraph Partitioning

    Gottesbüren, L., Heuer, T., Maas, N., Sanders, P., Schlag, S.: Scalable high-quality hypergraph partitioning. CoRR (2023). 10.48550/arXiv.2303.17679

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2303.17679 2023

  26. [26]

    Gottlob, G., Greco, G.: Decomposing combinatorial auctions and set packing prob- lems. J. ACM (4) (2013). 10.1145/2508028.2505987

    arXiv 2013

  27. [27]

    JGAA30(1), 1–24 (Jan 2026)

    Großmann, E., Joos, F., Reinstädtler, H., Schulz, C.: Engineering hypergraphb- matching algorithms. JGAA30(1), 1–24 (Jan 2026). 10.7155/jgaa.v30i1.3166

    work page doi:10.7155/jgaa.v30i1.3166 2026

  28. [28]

    In: 18th WAOA (2020)

    Hanguir, O., Stein, C.: Distributed algorithms for matching in hypergraphs. In: 18th WAOA (2020). 10.1007/978-3-030-80879-2_3

    work page doi:10.1007/978-3-030-80879-2_3 2020

  29. [29]

    Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximatingk-set pack- ing. Comput. Complex. (1) (2006). 10.1007/s00037-006-0205-6

    doi:10.1007/s00037-006-0205-6 2006

  30. [30]

    In: IPDPS 2010 (2010)

    Holtgrewe, M., Sanders, P., Schulz, C.: Engineering a scalable high quality graph partitioner. In: IPDPS 2010 (2010). 10.1109/IPDPS.2010.5470485

    arXiv 2010

  31. [31]

    10.1145/800057.808690

    Karp, R.M., Wigderson, A.: A fast parallel algorithm for the maximal independent set problem (1984). 10.1145/800057.808690

    arXiv 1984

  32. [32]

    Annals of Discrete Mathematics (1978)

    Korte, B., Hausmann, D.: An analysis of the greedy algorithm for independence systems. Annals of Discrete Mathematics (1978). 10.1007/BF01917662

    work page doi:10.1007/bf01917662 1978

  33. [33]

    In: 17th ACM symposium on Theory of computing (1985)

    Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: 17th ACM symposium on Theory of computing (1985). 10.1145/22145.22146

    arXiv 1985

  34. [34]

    In: SC24 (2024)

    Mandulak, M., Ghosh, S., Ferdous, S., Halappanvar, M., Slota, G.: Efficient weighted graph matching on gpus. In: SC24 (2024). 10.1109/SC41406.2024.00024

    Pith/arXiv arXiv 2024

  35. [35]

    In: IPDPS 2014

    Manne, F., Halappanavar, M.: New effective multithreaded matching algorithms. In: IPDPS 2014. IEEE (2014). 10.1109/IPDPS.2014.61

    work page doi:10.1109/ipdps.2014.61 2014

  36. [36]

    10.18637/jss.v008.i14

    Marsaglia, G.: Xorshift rngs (01 2003). 10.18637/jss.v008.i14

    doi:10.18637/jss.v008.i14 2003

  37. [37]

    10.1109/HiPC.2015.15

    Naim, M., Manne, F., Halappanavar, M., Tumeo, A., Langguth, J.: Optimizing approximate weighted matching on nvidia kepler k40. 10.1109/HiPC.2015.15

    work page doi:10.1109/hipc.2015.15 2015

  38. [38]

    The Limits of Local Search for the Maximum Weight Independent Set Problem in d-Claw Free Graphs

    Neuwohner, M.: The limits of local search for the maximum weight independent set problem in d-claw free graphs. CoRR (2021). 10.48550/arXiv.2106.03555

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2106.03555 2021

  39. [39]

    In: SODA 2023

    Neuwohner, M.: Passing the limits of pure local search for weightedk-set packing. In: SODA 2023. SIAM (2023). 10.1137/1.9781611977554.ch41

    doi:10.1137/1.9781611977554.ch41 2023

  40. [40]

    Park, S.K., Miller, K.W.: Random number generators: Good ones are hard to find. Commun. ACM (10) (1988). 10.1145/63039.63042 18 H. Reinstädtler et al

    arXiv 1988

  41. [41]

    Information Processing Letters (6) (2004)

    Pettie, S., Sanders, P.: A simpler linear time 2/3-εapproximation for maximum weight matching. Information Processing Letters (6) (2004). https://doi.org/10.1016/j.ipl.2004.05.007

    work page doi:10.1016/j.ipl.2004.05.007 2004

  42. [42]

    In: STACS 99 (1999)

    Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted match- ing in general graphs. In: STACS 99 (1999). 10.1007/3-540-49116-3_24

    work page doi:10.1007/3-540-49116-3_24 1999

  43. [43]

    In: ESA 2025 (2025)

    Reinstädtler, H., Ferdous, S.M., Pothen, A., Uçar, B., Schulz, C.: Semi- Streaming Algorithms for Hypergraph Matching. In: ESA 2025 (2025). 10.4230/LIPIcs.ESA.2025.79

    work page doi:10.4230/lipics.esa.2025.79 2025

  44. [44]

    10.5281/zenodo.15778413

    Reinstädtler, H., Ferdous, S., Pothen, A., Uçar, B., Schulz, C.: Wiki hypergraphs (2025). 10.5281/zenodo.15778413

    work page doi:10.5281/zenodo.15778413 2025

  45. [45]

    In: IEEE IPDPS 2024 (2024)

    Schwing, G., Grosu, D., Schwiebert, L.: Shared-memory parallel edmonds blossom algorithm for maximum cardinality matching in general graphs. In: IEEE IPDPS 2024 (2024). 10.1109/IPDPSW63119.2024.00107

    arXiv 2024

  46. [46]

    10.1109/MCSE.2021.3098509

    Trott, C., Berger-Vergiat, L., Poliakoff, D., Rajamanickam, S., Lebrun-Grandie, D., Madsen, J., Al Awar, N., Gligoric, M., Shipman, G., Womeldorff, G.: The kokkos ecosystem (2021). 10.1109/MCSE.2021.3098509

    arXiv 2021

  47. [47]

    Vigna, S.: An experimental exploration of marsaglia’s xorshift generators, scram- bled (2016),arxiv.org/abs/1402.6246

    Pith/arXiv arXiv 2016

  48. [48]

    10.1145/2228360.2228500

    Viswanathan, N., Alpert, C.J., Sze, C.C.N., Li, Z., Wei, Y.: DAC 2012 routability- driven placement contest and benchmark suite (2012). 10.1145/2228360.2228500

    arXiv 2012

  49. [49]

    Algorithmica (2) (1994)

    Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory, i: Two-level memo- ries. Algorithmica (2) (1994). 10.1007/BF01185207 Efficient Parallel Algorithms for Hypergraph Matching 19 A Work per Round on the CREW model Theorem 4.The CREW PRAM algorithm runs inO((log∆+logd) logm)time andO((κ) logm)work w.h.p. Proof.One round of Algorithm 2 consists of...

    arXiv 1994

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.