Pith. sign in

REVIEW 1 cited by

Deterministic Parallel High-Quality Hypergraph Partitioning

T0 review · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read DetJet and DetFlows are the first deterministic parallel hypergraph partitioners whose quality matches or beats non-deterministic state-of-the-art solvers, at a modest time cost.

arxiv 2504.12013 v2 pith:WBHLQTXY submitted 2025-04-16 cs.DC

Robert Krause , Lars Gottesbüren , Nikolai Maas This is my paper · ORCID
classification cs.DC
keywords deterministicnon-deterministicparallelalgorithmalgorithmsqualityrefinementwhile
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

Hypergraph partitioning splits a large set of vertices into blocks of similar size while minimizing how often hyperedges cross block boundaries. It is used in chip design, scientific computing, and database sharding. The multilevel approach repeatedly contracts vertices into smaller hypergraphs, computes an initial partitioning, then uncontracts while applying local search called refinement. Refinement is where the best parallel solvers became non-deterministic: threads move vertices asynchronously and race conditions make the result depend on scheduling.

This paper makes two refinement steps deterministic without giving up quality. First, DetJet generalizes the GPU graph refinement algorithm Jet to hypergraphs. Jet allows moves that temporarily violate the balance constraint and later repairs the balance, which lets it escape local minima. The authors add an efficient hypergraph afterburner that simulates move orders without quadratic work, and a new deterministic rebalancing step. Second, DetFlows handles flow-based refinement, normally the strongest and most expensive technique. They show that even though the underlying max-flow solver is non-deterministic, the particular minimum cuts used in refinement are unique, so the bipartition result is fixed. They schedule block pairs in a deterministic matching.

On standard benchmarks with 94 hypergraphs and 71 graphs, DetJet matches the quality of the non-deterministic Mt-KaHyPar default while running about 15% slower. DetFlows is about 1% better than the non-deterministic flow configuration and about 29% slower. The code and benchmark data are public.

Extended reading notes

Core claim

From the conclusion: 'We develop the first deterministic parallel algorithm for hypergraph partitioning that matches the quality of the best non-deterministic and sequential solvers.' If true, this means deterministic partitions no longer cost the quality penalty seen in BiPart and Mt-KaHyPar-SDet; DetJet matches Mt-KaHyPar-Default at a 15% time increase, and DetFlows beats Mt-KaHyPar-Flows by about 1% at a 31% time increase.

Load-bearing premise

The determinism claim depends on every parallel step being order-independent or deterministically tie-broken. The paper gives a clean argument for flow-based refinement via unique min cuts, but Algorithm 2 sorts pins by gain only, with no tie-break rule stated, and Section 5.2 schedules a maximal matching in the quotient graph with no tie-break rule stated. If equal-gain moves or equal-priority matching edges are processed in different orders across runs, recomputed gains and the final partition could differ. This is a load-bearing assumption for the central 'deterministic' claim, and it is distinct from the quality-versus-time claims.

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.

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

No new physical or mathematical entities are introduced. The paper's contributions are algorithmic; its only postulates are the four axioms above and the four tuned parameters listed here.

free parameters (4)
  • Temperature schedule tau = three rounds decreasing from 0.75 to 0
    Jet parameter controlling which negative-gain moves enter the afterburner; Section 7.3 selects the schedule on the evaluation benchmarks.
  • Deadzone factor d = 0.1
    Rebalancing target-block deadzone size chosen based on preliminary experiments in Section 4.3.
  • Jet iteration limit = 8
    Maximum iterations without quality improvement set to 8 because it worked best in preliminary experiments, Section 7.3.
  • Number of temperature rounds = 3
    Selected from the quality-versus-time trade-off on the benchmarks, Section 7.3.
assumptions (4)
  • domain assumption The multilevel paradigm (coarsen, initial partition, refine) improves solutions for hypergraph partitioning.
    Assumed throughout; standard in the cited literature, not derived here.
  • standard math In a residual graph of a maximum flow, the vertices reachable from the source and sink induce the unique inclusion-minimal source-side and minimal sink-side minimum cuts (Picard-Queyranne).
    Basis for deterministic two-way refinement in Section 5.1; standard theorem for graphs, applied to the hypergraph flow network.
  • domain assumption Parallel sorting, prefix sums, and integer atomic adds are deterministic in the implementation.
    Required for the determinism claim; the paper specifies tie-breaking only for piercing candidates, not for afterburner sorts or maximal matching.
  • domain assumption The benchmark instances are representative of practical hypergraph partitioning workloads.
    Evaluation and parameter tuning rely on the three benchmark sets; generalization beyond them is assumed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deterministic Parallel High-Quality Hypergraph Partitioning." pith.science (2026). https://pith.science/paper/WBHLQTXY

@misc{pith2026250412013,
  author       = {Pith},
  title        = {Pith review of: Deterministic Parallel High-Quality Hypergraph Partitioning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WBHLQTXY}},
  note         = {Machine review of arXiv:2504.12013}
}
abstract

We present a deterministic parallel multilevel algorithm for balanced hypergraph partitioning that matches the state of the art for non-deterministic algorithms. Deterministic parallel algorithms produce the same result in each invocation, which is crucial for reproducibility. Moreover, determinism is highly desirable in application areas such as VLSI design. While there has been tremendous progress in parallel hypergraph partitioning algorithms recently, deterministic counterparts for high-quality local search techniques are missing. Consequently, solution quality is severely lacking in comparison to the non-deterministic algorithms. In this work we close this gap. First, we present a generalization of the recently proposed Jet refinement algorithm. While Jet is naturally amenable to determinism, significant changes are necessary to achieve competitive performance on hypergraphs. We also propose an improved deterministic rebalancing algorithm for Jet. Moreover, we consider the powerful but slower flow-based refinement and introduce a scheme that enables deterministic results while building upon a non-deterministic maximum flow algorithm. As demonstrated in our thorough experimental evaluation, this results in the first deterministic parallel partitioner that is competitive to the highest quality solvers. With Jet refinement, we match or exceed the quality of Mt-KaHyPar's non-deterministic default configuration while being only 15\% slower on average. We observe self-relative speedups of up to 55 on 64 cores with a 22.5$\times$ average speedup. Our deterministic flow-based refinement exceeds the quality of the non-deterministic variant by roughly 1\% on average but requires 31\% more running time.

Figures

Figures reproduced from arXiv: 2504.12013 by the authors.

Figure 1
Figure 1. The quality gap between non-deterministic [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 1
Figure 1. This is due to the lack of high-quality refine [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Venn diagram style visualization of the vertex sets during flow-based refinement. Flow augmentation [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figures from the paper (8 more)
Figure 3
Figure 3. Figure 3: Impact of improved coarsening on solution [PITH_FULL_IMAGE:figures/full_fig_p009_3.png]
Figure 4
Figure 4. Figure 4: Comparison of solution quality for different temperature settings for Jet refinement on hypergraphs [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 6
Figure 6. Figure 6: Solution quality on all instances for differ [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Strong scalability results for our Jet refine [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Comparing DetJet to state-of-the-art partitioners on hypergraphs (left), irregular graphs (center) and [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Comparing the solution quality of determinis [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 11
Figure 11. Figure 11: Ablation study of coarsening improvements for final solution quality (left) and solution quality after [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 12
Figure 12. Figure 12: Running time shares of different components of the DetJet configuration on all instances. The x-axis [PITH_FULL_IMAGE:figures/full_fig_p018_12.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Linear-Time Multilevel Graph Partitioning via Edge Sparsification

    cs.DS 2025-04 conditional novelty 7.0 of 10

    A multilevel graph partitioner with edge sparsification achieves proven linear expected work and a 1.49x average speedup in KaMinPar with only about 1% average cut increase.

Reference graph

Works this paper leans on

59 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    Engineering a Direct k- way Hypergraph Partitioning Algorithm

    Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Engineering a Direct k- way Hypergraph Partitioning Algorithm. In 19th Workshop on Algorithm Engineering & Experiments (ALENEX), pages 28–42, 2017. doi:10.1137/1. 9781611974768.3

    doi:10.1137/1 2017

  2. [2]

    High-Quality Shared-Memory Graph Parti- tioning

    Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. High-Quality Shared-Memory Graph Parti- tioning. In 24th European Conference on Parallel Processing (Euro-Par), pages 659–671. Springer, 8

    work page

  3. [3]

    Alpert and Andrew B

    Charles J. Alpert and Andrew B. Kahng. Re- cent Directions in Netlist Partitioning: A Sur- vey. Integration, 19(1-2):1–81, 1995. doi:10.1016/ 0167-9260(95)00008-4

    work page 1995

  4. [4]

    Lewis, Ana-Maria Oros-Peusquens, Nadim J

    Katrin Amunts, Claude Lepage, Louis Borgeat, Hartmut Mohlberg, Timo Dickscheid, Marc- ´Etienne Rousseau, Sebastian Bludau, Pierre-Louis Bazin, Lindsay B. Lewis, Ana-Maria Oros-Peusquens, Nadim J. Shah, Thomas Lippert, Karl Zilles, and Alan C. Evans. BigBrain: An Ultrahigh-Resolution 3D Human Brain Model. Science, 340(6139):1472– 1475, 2013

    work page 2013

  5. [5]

    Bal- anced Graph Partitioning

    Konstantin Andreev and Harald R¨ acke. Bal- anced Graph Partitioning. In 16th ACM Sympo- sium on Parallelism in Algorithms and Architec- tures (SPAA), pages 120–124, 2004. doi:10.1145/ 1007912.1007931

    arXiv 2004

  6. [6]

    Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner

    David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partitioning and Graph Clustering , volume 588. American Math- ematical Society Providence, 2013. doi:10.1090/ conm/588

    work page 2013

  7. [7]

    Blelloch, and Julian Shun

    Niklas Baumstark, Guy E. Blelloch, and Julian Shun. Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm. In 23th European Symposium on Algorithms (ESA) , pages 106–117. Springer, 2015. doi:10.1007/978-3-662-48350-3\ _10

    doi:10.1007/978-3-662-48350-3 2015

  8. [8]

    The SAT Competition 2014

    Anton Belov, Daniel Diepold, Marijn Heule, and Matti J¨ arvisalo. The SAT Competition 2014. http: //www.satcompetition.org/2014/, 2014

    work page 2014

Show all 59 references
  1. [9]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian Shun. Internally Deterministic Parallel Algorithms Can Be Fast. In 17th ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 181–192, 2012. doi: 10.1145/2145816.2145840

    2012

  2. [10]

    Parallel Programming Must Be Deterministic By Default

    Robert L Bocchino, Vikram Adve, Sarita Adve, and Marc Snir. Parallel Programming Must Be Deterministic By Default. Usenix HotPar, 6, 2009

    2009

  3. [11]

    UbiCrawler: A Scalable Fully Distributed Web Crawler

    Paolo Boldi, Bruno Codenotti, Massimo Santini, and Sebastiano Vigna. UbiCrawler: A Scalable Fully Distributed Web Crawler. Software: Practice & Experience, 34(8):711–726, 2004. doi:10.1002/SPE. 587

    2004 doi

  4. [12]

    Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Com- pressing Social Networks

    Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Com- pressing Social Networks. In 20th International Con- ference on World Wide Web (WWW), pages 587–596,

  5. [13]

    The WebGraph Framework I: Compression Techniques

    Paolo Boldi and Sebastiano Vigna. The WebGraph Framework I: Compression Techniques. In13th Inter- national Conference on World Wide Web (WWW) , pages 595–601, 2004. doi:10.1145/988672.988752

    2004

  6. [14]

    Recent Advances in Graph Partitioning

    Aydin Bulu¸ c, Henning Meyerhenke, Ilya Safro, Pe- ter Sanders, and Christian Schulz. Recent Advances in Graph Partitioning. In Algorithm Engineering , volume 9220, pages 117–158. 2016. doi:10.1007/ 978-3-319-49487-6_4

    2016

  7. [15]

    More Recent Ad- vances in (Hyper)Graph Partitioning

    ¨Umit C ¸ ataly¨ urek, Karen Devine, Marcelo Faraj, Lars Gottesb¨ uren, Tobias Heuer, Henning Meyer- henke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, et al. More Recent Ad- vances in (Hyper)Graph Partitioning. ACM Com- puting Surveys, 55(12):253–253, ...

    2023

  8. [16]

    PT- Scotch: A Tool for Efficient Parallel Graph Ordering

    C´ edric Chevalier and Fran¸ cois Pellegrini. PT- Scotch: A Tool for Efficient Parallel Graph Ordering. Parallel Computing , 34(6-8):318–331, 2008. doi: 10.1016/j.parco.2007.12.001

    2008 doi

  9. [17]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software , 38(1):1:1–1:25, 11 2011. doi:10.1145/2049662.2049663

    2011

  10. [18]

    Devine, Erik G

    Karen D. Devine, Erik G. Boman, Robert T. Hea- phy, Rob H. Bisseling, and ¨Umit V. Cataly¨ urek. Par- allel Hypergraph Partitioning for Scientific Comput- ing. In 20th International Parallel and Distributed Processing Symposium (IPDPS) . IEEE, 2006. doi: 10.1109/IPDPS.2006.1639359

    2006 arXiv

  11. [19]

    Dolan and Jorge J

    Elizabeth D. Dolan and Jorge J. Mor´ e. Bench- marking Optimization Software with Performance Profiles. Mathematical Programming, 91(2):201–213,

  12. [20]

    Fiduccia and Robert M

    Charles M. Fiduccia and Robert M. Mattheyses. A Linear-Time Heuristic for Improving Network Parti- tions. In 19th Design Automation Conference (DAC), pages 175–181, 1982. doi:10.1145/800263.809204

    1982

  13. [21]

    Gilbert, Kamesh Madduri, Erik G

    Michael S. Gilbert, Kamesh Madduri, Erik G. Boman, and Siva Rajamanickam. Jet: Multilevel Graph Partitioning on Graphics Processing Units. SIAM Journal of Scientific Computing. , 46(5):700,

  14. [22]

    Gilbert, Kamesh Madduri, Erik G

    Michael S. Gilbert, Kamesh Madduri, Erik G. Bo- man, and Sivasankaran Rajamanickam. Jet: Mul- tilevel Graph Partitioning on GPUs, 2023. arXiv: 2304.13194, doi:10.48550/arXiv.2304.13194

    2023 doi arXiv

  15. [23]

    Deter- ministic Parallel Hypergraph Partitioning

    Lars Gottesb¨ uren and Michael Hamann. Deter- ministic Parallel Hypergraph Partitioning. In 28th European Conference on Parallel Processing (Euro- Par), pages 301–316. Springer, 2022. doi:10.1007/ 978-3-031-12597-3\_19

    2022

  16. [24]

    Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

    Lars Gottesb¨ uren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In 27th European Sympo- sium on Algorithms (ESA) , pages 52:1–52:17, 2019. doi:10.4230/LIPIcs.ESA.2019.52

    2019 doi

  17. [25]

    Scalable High- Quality Hypergraph Partitioning

    Lars Gottesb¨ uren, Tobias Heuer, Nikolai Maas, Peter Sanders, and Sebastian Schlag. Scalable High- Quality Hypergraph Partitioning. ACM Transactions on Algorithms , 20(1):9:1–9:54, 2024. doi:10.1145/ 3626527

    2024

  18. [26]

    Parallel Flow-Based Hypergraph Partition- ing

    Lars Gottesb¨ uren, Tobias Heuer, and Peter Sanders. Parallel Flow-Based Hypergraph Partition- ing. In 20th International Symposium on Experimen- tal Algorithms (SEA) , volume 233 of LIPIcs, pages 5:1–5:21, 2022. doi:10.4230/LIPICS.SEA.2022.5

    2022 doi

  19. [27]

    Shared-Memory n-level Hy- pergraph Partitioning

    Lars Gottesb¨ uren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Shared-Memory n-level Hy- pergraph Partitioning. In 24st Workshop on Algo- rithm Engineering & Experiments (ALENEX) , 2022. doi:10.1137/1.9781611977042.11

    2022 doi

  20. [28]

    Advanced Flow-Based Multilevel Hypergraph Partitioning

    Lars Gottesb¨ uren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced Flow-Based Multilevel Hypergraph Partitioning. In 18th In- ternational Symposium on Experimental Algorithms (SEA), pages 11:1–11:15, 2020. doi:10.4230/ LIPIcs.SEA.2020.11

    2020

  21. [29]

    Scalable Shared-Memory Hy- pergraph Partitioning

    Lars Gottesb¨ uren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Scalable Shared-Memory Hy- pergraph Partitioning. In 23st Workshop on Algo- rithm Engineering & Experiments (ALENEX) , 2021. doi:10.1137/1.9781611976472.2

    2021 doi

  22. [30]

    Deep Mul- tilevel Graph Partitioning

    Lars Gottesb¨ uren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier. Deep Mul- tilevel Graph Partitioning. In 29th European Sym- posium on Algorithms (ESA) , volume 204 of LIPIcs, pages 48:1–48:17, 2021. doi:10.4230/LIPIcs.ESA. 2021.48

    2021 doi

  23. [31]

    Graph Bi- section with Pareto-Optimization

    Michael Hamann and Ben Strasser. Graph Bi- section with Pareto-Optimization. In 18th Work- shop on Algorithm Engineering & Experiments (ALENEX), pages 90–102. SIAM, 2016. doi:10. 1137/1.9781611974317.8

    2016

  24. [32]

    A Mul- tilevel Algorithm for Partitioning Graphs

    Bruce Hendrickson and Robert Leland. A Mul- tilevel Algorithm for Partitioning Graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993

    1993

  25. [33]

    Network Flow-Based Refinement for Multilevel Hy- pergraph Partitioning

    Tobias Heuer, Peter Sanders, and Sebastian Schlag. Network Flow-Based Refinement for Multilevel Hy- pergraph Partitioning. ACM Journal of Experimen- tal Algorithmics (JEA) , 24(1):2.3:1–2.3:36, 09 2019. doi:10.1145/3329872

    2019 doi

  26. [34]

    Improv- ing Coarsening Schemes for Hypergraph Partition- ing by Exploiting Community Structure

    Tobias Heuer and Sebastian Schlag. Improv- ing Coarsening Schemes for Hypergraph Partition- ing by Exploiting Community Structure. In 16th In- ternational Symposium on Experimental Algorithms (SEA), pages 21:1–21:19, 06 2017. doi:10.4230/ LIPIcs.SEA.2017.21

    2017

  27. [35]

    Engineering a Scalable High Quality Graph Partitioner

    Manuel Holtgrewe, Peter Sanders, and Christian Schulz. Engineering a Scalable High Quality Graph Partitioner. IEEE Transactions on Parallel and Distributed Systems, pages 1–12, 2010

    2010

  28. [36]

    Steele Jr

    Guy L. Steele Jr. Making Asynchronous Paral- lelism Safe for the World. In 17th ACM Symposium on Principles of Programming Languages (POPL) , pages 218–231. ACM Press, 1990. doi:10.1145/ 96709.96731

    1990

  29. [37]

    Multilevel Hypergraph Parti- tioning: Applications in VLSI Domain

    George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Parti- tioning: Applications in VLSI Domain. IEEE Trans- actions on Very Large Scale Integration (VLSI) Sys- tems, 7(1):69–79, 1999. doi:10.1109/92.748202

    1999 doi

  30. [38]

    Multi- threaded Graph Partitioning

    Dominique Lasalle and George Karypis. Multi- threaded Graph Partitioning. In 27th IEEE Inter- national Symposium on Parallel and Distributed Pro- cessing (IPDPS) , pages 225–236, 2013. doi:10. 1109/IPDPS.2013.50

    2013

  31. [39]

    Edward A. Lee. The Problem with Threads. Com- puter, 39(5):33–42, 2006. doi:10.1109/MC.2006. 180

    2006 doi

  32. [40]

    Parallel Unconstrained Local Search for Partitioning Irregular Graphs

    Nikolai Maas, Lars Gottesb¨ uren, and Daniel Seemaier. Parallel Unconstrained Local Search for Partitioning Irregular Graphs. In 26st Work- shop on Algorithm Engineering & Experiments (ALENEX), pages 32–45. SIAM, 2024. doi:10. 1137/1.9781611977929.3

    2024

  33. [41]

    BiPart: A Parallel and Deter- ministic Multilevel Hypergraph Partitioner

    Sepideh Maleki, Udit Agarwal, Martin Burtscher, and Keshav Pingali. BiPart: A Parallel and Deter- ministic Multilevel Hypergraph Partitioner. In 26th ACM Symposium on Principles and Practice of Par- allel Programming (PPOPP) , pages 161–174, 2021. doi:10.1145/3437801.3441611

    2021

  34. [42]

    Growth of the Flickr Social Network

    Alan Mislove, Hema Swetha Koppula, Krishna P Gummadi, Peter Druschel, and Bobby Bhattachar- jee. Growth of the Flickr Social Network. In 1st Workshop on Online Social Networks (WOSN), pages 25–30. ACM, 2008. doi:10.1145/1397735.1397742

    2008

  35. [43]

    Papa and Igor L

    David A. Papa and Igor L. Markov. Hypergraph Partitioning and Clustering. In Handbook of Approxi- mation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. doi:10.1201/9781420010749. ch61

    2007 doi

  36. [44]

    On the Structure of All Minimum Cuts in a Network and Applications

    Jean-Claude Picard and Maurice Queyranne. On the Structure of All Minimum Cuts in a Network and Applications. Mathematical Programming, 22(1):121,

  37. [45]

    Near Linear Time Algorithm to Detect Community Structures in Large-Scale Net- works

    Usha Nandini Raghavan, R´ eka Albert, and Soundar Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Net- works. Physical Review E , 76(3):036106, 2007. doi: 10.1103/PhysRevE.76.036106

    2007 doi

  38. [46]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization. In 29th Conference on Artificial Intelligence (AAAI) , 2015. URL: http: //networkrepository.com

    2015

  39. [47]

    Engineering Multilevel Graph Partitioning Algorithms

    Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In 19th European Symposium on Algorithms (ESA) , pages 469–480, 2011. doi:10.1007/978-3-642-23719-5\ _40

    2011 doi

  40. [48]

    Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning

    Peter Sanders and Daniel Seemaier. Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning. In 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 443–445. ACM, 2024. doi:10.1145/3626183.3660257

    2024

  41. [49]

    High-Quality Hypergraph Partition- ing

    Sebastian Schlag, Tobias Heuer, Lars Gottesb¨ uren, Yaroslav Akhremtsev, Christian Schulz, and Pe- ter Sanders. High-Quality Hypergraph Partition- ing. ACM Journal of Experimental Algorithmics , 27:1.9:1–1.9:39, 2022. doi:10.1145/3529090

    2022 doi

  42. [50]

    Social Hash: An Assignment Framework for Optimizing Distributed Systems Operations on Social Networks

    Alon Shalita, Brian Karrer, Igor Kabiljo, Arun Sharma, Alessandro Presta, Aaron Adcock, Herald Kllapi, and Michael Stumm. Social Hash: An Assignment Framework for Optimizing Distributed Systems Operations on Social Networks. In 13th USENIX Symposium on Networked Systems Design...

    2016

  43. [51]

    Simon and Shang-Hua Teng

    Horst D. Simon and Shang-Hua Teng. How Good is Recursive Bisection? SIAM Journal of Scientific Computing, 18(5):1436–1445, 1997. doi:10.1137/ S1064827593255135

    1997

  44. [52]

    Alpert, Cliff C

    Natarajan Viswanathan, Charles J. Alpert, Cliff C. N. Sze, Zhuo Li, and Yaoguang Wei. The DAC 2012 Routability-Driven Placement Contest and Benchmark Suite. In 49th Conference on Design Automation (DAC) , pages 774–782. ACM, 6 2012. doi:10.1145/2228360.2228500

    2012

  45. [53]

    Char- acterizing Tweeting Behaviors of Sina Weibo Users via Public Data Streaming

    Kai Zhang, Qian Yu, Kai Lei, and Kuai Xu. Char- acterizing Tweeting Behaviors of Sina Weibo Users via Public Data Streaming. In Web-Age Informa- tion Management , pages 294–297. Springer, 2014. doi:10.1007/978-3-319-08010-9\_32

    2014 doi

  46. [54]

    Cataly¨ urek and Cevdet Aykanat

    ¨Umit V. Cataly¨ urek and Cevdet Aykanat. Hypergraph-Partitioning-based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems , 10(7):673–693, 1999. doi:10.1109/71.780863. A Additional Details on the Benchmark Set...

    1999

  47. [1982]

    doi:10.1007/BF01581031

    doi

  48. [2002]

    doi:10.1007/s101070100263

    doi

  49. [2011]

    doi:10.1145/1963405.1963488

  50. [2018]

    doi:10.1007/978-3-319-96983-1\_47

    doi

  51. [2024]

    doi:10.1137/23M1559129

    doi

Pith tools

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