Pith. sign in

REVIEW 3 major objections 4 minor 34 references

Near-Optimal Minimum Cuts in Hypergraphs at Scale

T0 review · 3 major / 4 minor · 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 A new solver, HeiCut, claims that exact contraction rules guided by an upper bound can find the minimum cut of most real hypergraphs directly, with a relaxed binary program covering the rest.

desk verdict A genuinely useful engineering paper with a real correctness bug in the fully-reduced branch: as written, Algorithm 1 returns 0 on a single weighted hyperedge, so the exactness claim needs a fix before the results can be trusted. read the letter →

arxiv 2504.19842 v2 pith:ZIJKD2ZJ submitted 2025-04-28 cs.DS

Adil Chhabra , Christian Schulz , Bora Uçar , Loris Wilwert This is my paper · ORCID
classification cs.DS
keywords HeiCuthypergraphminimumexactreductionscontractionrulesrelaxedbinaryintegerprogramlabelpropagationenumerationlarge-scaleanalysis
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

HeiCut is a solver for the hypergraph minimum cut problem—splitting vertices into two nonempty blocks to minimize the total weight of hyperedges crossing the split. The paper claims that a small set of provably exact contraction rules, guided by an upper bound $\hat{\lambda}$ on the minimum cut, shrinks most real hypergraphs to a trivial instance: in over 85% of the 500+ tested instances the exact minimum cut is found by reduction alone. Only when reductions stall does HeiCut solve a relaxed binary integer linear program on the reduced hypergraph, producing a near-optimal cut. If these claims hold, HeiCut makes exact or near-exact hypergraph min-cuts practical on instances that previous solvers cannot finish, while also handling weighted hypergraphs that the leading unweighted method cannot.

What carries the argument

The load-bearing mechanism is the pair $(\hat{\lambda}, \text{contraction rules})$: $\hat{\lambda}$, initialized to the minimum weighted vertex degree and tightened after each contraction, is the threshold below which a cut would have to be interesting. Each exact reduction rule identifies a set of vertices—a heavy hyperedge, an overlap of hyperedges, a nested substructure, or a graph-style heavy neighborhood—whose separation would force a cut of weight at least $\hat{\lambda}$, so contracting it cannot raise the true minimum cut. Three rules (ImbalancedVertex, ImbalancedTriangle, HeavyNeighborhood) come from the graph reduction literature and are applied to size-2 hyperedges; the paper notes one must use a strict inequality in ImbalancedVertex because a non-strict version can contract two equal-weight edges sharing a vertex and destroy the minimum cut. The final stage is a relaxed BIP on the reduced instance, which the reductions make unnecessary for most inputs.

What would settle it

Enumerate all small hypergraphs (say, up to seven vertices with unit or small integer weights), compute the true minimum cut by brute force, and run HeiCut's exact-reduction pipeline on each; any instance where the reduced hypergraph's minimum cut exceeds the original minimum cut—especially one where Rule 2 contracts a hyperedge of weight exactly $\hat{\lambda}$ while the unique minimum cut separates its endpoints—would falsify the claim that the reductions are exact.

Watch

Extended reading notes

Core claim

The paper's central claim is that aggressive but safe contraction can reduce hypergraph minimum cut computation to a tiny residual problem. HeiCut initializes an upper bound $\hat{\lambda}$ from the minimum weighted vertex degree and applies seven reduction rules—removing trivial hyperedges, contracting heavy hyperedges, heavy overlaps, nested substructures, and three rules adapted from graph cuts—each designed so that any cut crossing the contracted structure has value at least $\hat{\lambda}$ and therefore cannot improve on the best cut already known. On real-world and synthetic hypergraphs, this pipeline alone fully reduces 85–95% of instances, meaning the exact minimum cut is known without any optimization. For the remainder, a relaxed BIP (binary variables allowed to take near-binary float values, then rounded) computes a cut the experiments show matches the exact value on every instance where an exact baseline could be compared. The paper further claims that HeiCut solves over twice as many instances as the prior state of the art within fixed time and memory limits, and is up to five orders of magnitude faster.

Load-bearing premise

A contracted set might, in principle, be separated by every genuinely minimum cut, and the paper does not fully prove that this never happens; if it did, the reduced instance could have a larger minimum cut than the original hypergraph.

Editorial extensions

If this is right

  • Exact hypergraph minimum cuts become routinely computable on the 85–95% of instances that fully reduce, since no optimization solver is needed after contraction.
  • Weighted hypergraphs, which the previous k-trimmer baseline cannot handle, become solvable by the same pipeline.
  • On large hypergraphs, HeiCut scales to about twice as many instances as the state of the art under the same time and memory limits, and runs up to five orders of magnitude faster.
  • The label-propagation variant trades a little solution quality for lower memory on hard instances, and is faster than plain HeiCut on the synthetic (k,2)-core benchmark.
  • The new (k,2)-core hypergraph dataset gives future work instances where the minimum cut is genuinely smaller than the trivial degree cut.

Reading between the lines

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

  • If the reduction rules are as effective as reported, then the difficulty of hypergraph min-cut is concentrated in a small 'core' that survives contraction; studying the structure of those cores could yield even stronger reductions.
  • The near-exactness of the relaxed BIP suggests the LP relaxation of the cut formulation may be integral or near-integral on real instances; a systematic integrality-gap study on the reduced cores would be a natural next test.
  • The same reduction framework might transfer to related problems such as sparsest cut, s-t min-cut, or hypergraph clustering, since the reductions only rely on lower bounds for crossing cuts.
  • A formal invariant stating that every destroyed minimum cut is represented either by $\hat{\lambda}$ or by a cut in the reduced hypergraph would turn the empirical exactness into a theorem; Figure 2's counterexample shows the subtlety of such proofs.
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.

Referee Report

3 major / 4 minor

Summary. The paper presents HeiCut, a solver for the (near-optimal) minimum cut problem in weighted and unweighted hypergraphs. HeiCut interleaves seven contraction rules, some adapted from graph algorithms and some novel for hypergraphs, with an optional label-propagation heuristic, and then solves a relaxed binary integer program (BIP) on the reduced hypergraph. The authors report that the exact reductions alone fully reduce 85--95% of the instances in the MHG and LHG benchmarks, and that HeiCut outperforms a reimplementation of the Chekuri--Xu Trimmer algorithm and a standalone Gurobi-based relaxed BIP on more than 500 real and synthetic instances, by up to five orders of magnitude in runtime.

Significance. If the correctness issues described below are repaired, this is a useful algorithmic-engineering contribution: it combines safe-contraction ideas with a relaxed BIP to extend the scale on which hypergraph minimum cuts can be computed, and it provides a broad benchmark, including a new synthetic k-core family, with three baselines. The paper is honest that the BIP relaxation is inexact, and the experimental evaluation is broad and internally consistent. The exactness claims for the reduction rules are, however, load-bearing and currently not supported by the pseudocode and proofs as written.

major comments (3)
  1. [Algorithm 1, lines 9-13] The algorithm returns the wrong value on a trivial instance. Let H have V={u,v}, one hyperedge e={u,v} with omega(e)=5, and no other hyperedges. The true minimum cut is lambda(H)=5. The algorithm initializes lambda_hat to min_v d_omega(v)=5, Reduction Rule 2 applies because omega(e)>=lambda_hat, and after contracting e the hypergraph has one vertex and no hyperedges. Line 9 then sets lambda_hat <- min(5, delta_omega(H))=0, and line 10 fires, returning lambda=0. This is not even a valid cut value of the input hypergraph. The update in line 9 is invalid when the reduced hypergraph has one vertex, because the singleton 'cut' of a one-vertex hypergraph corresponds to the empty or full vertex set of the original hypergraph. The fully-reduced branch must not return 0 before considering the case |V|=1, and lambda_hat must not be lowered using a one-vertex reduced graph.
  2. [Section 3.1, Reduction Rule 2; Algorithm 1, line 15] The proofs of Rules 2, 3, and 7 only establish that a cut crossing the contracted structure has value at least lambda_hat. They do not establish that every minimum cut of the original hypergraph is represented by a minimum cut of the reduced hypergraph, and the final output can therefore be strictly larger than the true optimum. Concretely, take vertices a,b,c,d,e with hyperedges {a,b} of weight 5, {a,c} of weight 10, and {c,d}, {d,e}, {e,c} of weight 6. The minimum cut is 5, realized by {b} versus the rest, and lambda_hat = d_omega(b)=5. Rule 2 contracts {a,b}, producing a reduced hypergraph whose minimum cut is 10 (the cut {w} versus {c,d,e}, where w is the contracted vertex). Since line 15 returns SolveRelaxedBIP(H) rather than min(lambda_hat, SolveRelaxedBIP(H)), HeiCut would report 10. The correct invariant for this style of contraction is that every cut of value strictly below lambda_hat survives, and the output must be the minimum of the maintained upper bound and the reduced-instance optimum. As written, the final solution of the reduced instance is used alone, which contradicts the claim that the reductions preserve the minimum cut.
  3. [Section 3.1, first paragraph; Section 4.1] The statement that the reductions 'provably preserve the value of the minimum cut' is too strong for the rules as proved. The text says contractions preserve correctness because 'any minimum cut of the reduced hypergraph remains valid on the input hypergraph'; the counterexample in the previous comment shows this implication fails. What the proofs support is the weaker and standard statement that no cut of value less than lambda_hat is destroyed. This distinction matters for the claimed exactness of the 85-95% of instances that are fully reduced: for those instances the algorithm currently returns either 0 or the relaxed-BIP value of the reduced hypergraph, not the maintained upper bound. The experiments should be re-examined after fixing the algorithm to see how many instances were affected by this bug.
minor comments (4)
  1. [Section 3.2] The relaxed BIP section should explicitly state that no approximation guarantee is claimed for the rounding step; the sentence 'the practical difference is negligible' is an empirical observation, not a theorem, and should be phrased as such.
  2. [Abstract] There is a typo in 'fiveorders of magnitude'; a space is missing.
  3. [Section 3.1] The paragraph 'If the hypergraph is reduced to a single vertex or a set of isolated vertices, the minimum cut value has been determined' should be qualified: for a set of isolated vertices the value is 0, while for a single vertex after contractions the value is lambda_hat, not 0.
  4. [Section 4, Baselines] Because Trimmer is a reimplementation without a public reference implementation, it would strengthen the paper to state clearly which parts of the comparison could be affected by implementation differences, and to make the HeiCut and Trimmer code available at least as supplementary material.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity found; HeiCut's reductions are self-contained against an independent upper bound, and the Algorithm 1 zero-edge branch is a soundness bug rather than a circular step.

full rationale

Circularity check: no step of HeiCut's derivation is equivalent to its inputs by construction. The upper bound λhat = min_v dω(v) is an independent trivial-cut bound; the exact reduction rules are proved as inequalities against this bound (e.g., Rule 2: λ ≥ ω(e) ≥ λhat), and the relaxed BIP is an independent optimization formulation with no fitted parameters. No 'prediction' in the paper is defined in terms of the quantity being predicted. The self-citations to VieCut (co-authored by C. Schulz) are transparent attributions of inherited graph-based rules and an optional heuristic; the load-bearing correctness claims are argued from Padberg-Rinaldi [27] and from the paper's own reduction proofs, and the heuristic is independently evaluated in Section 4. I therefore find no significant circularity. A separate correctness defect exists outside circularity: Algorithm 1 (lines 10-11) returns λ = 0 when |E| = 0, which is wrong for a single weighted hyperedge {u,v} with weight 5 (true λ = 5); the Rule 2 proof only shows crossing cuts are ≥ λhat and does not show a minimum cut avoiding the contracted edge exists, so the fully-reduced branch discards the valid upper bound. This is a soundness bug, not a circularity, and does not raise the circularity score.

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

The central algorithm has no fitted physical constants and no invented entities. The free parameters are engineering thresholds and solver settings. The main externally assumed machinery is the correctness of prior graph reduction rules, MA-ordering exactness, and Chekuri-Xu trimming. The relaxed-BIP rounding assumption is the least supported axiom and is only empirically validated.

free parameters (4)
  • reduction_threshold_vertices = n_o = 1000
    Stopping threshold below which Relaxed-BIP is invoked; chosen by hand, affects runtime but not central correctness.
  • label_propagation_iterations = 1
    Optional heuristic; one iteration chosen in experiments; not used in the default comparison.
  • gurobi_tolerances = IntFeasTol = FeasibilityTol = 1e-7
    Numerical settings for Gurobi; hand-selected for higher precision.
  • random_weight_range = uniform [1,100]
    Used to create weighted versions of benchmark hypergraphs; experimental design choice.
assumptions (4)
  • standard math Padberg-Rinaldi reduction rules are correct for graph edges of size two.
    Rules 5 through 7 are inherited from [27], with Rule 5 adapted to a strict inequality. Correctness is assumed without reproof.
  • standard math Maximum-adjacency ordering yields exact minimum s-t cuts for the Trimmer baseline.
    The exact solver in the reimplemented Trimmer relies on MA ordering and Queyranne's submodular function algorithm, assumed from [20, 24, 29].
  • standard math Chekuri-Xu k-trimmed certificates preserve local connectivities up to k.
    The Trimmer baseline is built on the k-trimmed certificate construction from [6]; correctness is assumed from that paper.
  • ad hoc to paper Rounding the relaxed BIP solution yields a near-optimal cut in practice.
    The relaxed BIP is explicitly inexact and the paper offers empirical evidence on 145 instances rather than a formal guarantee.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Minimum Cuts in Hypergraphs at Scale." pith.science (2026). https://pith.science/paper/ZIJKD2ZJ

@misc{pith2026250419842,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Minimum Cuts in Hypergraphs at Scale},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZIJKD2ZJ}},
  note         = {Machine review of arXiv:2504.19842}
}
read the original abstract

The hypergraph minimum cut problem aims to partition its vertices into two blocks while minimizing the total weight of the cut hyperedges. This fundamental problem arises in network reliability, VLSI design, and community detection. We present HeiCut, a scalable algorithm for computing near-optimal minimum cuts in both unweighted and weighted hypergraphs. HeiCut aggressively reduces the hypergraph size through a sequence of provably exact reductions that preserve the minimum cut, along with an optional heuristic contraction based on label propagation. It then solves a relaxed Binary Integer Linear Program (BIP) on the reduced hypergraph to compute a near-optimal minimum cut. Our extensive evaluation on over 500 real-world hypergraphs shows that HeiCut computes the exact minimum cut in over 85% of instances using our exact reductions alone, and offers the best solution quality across all instances. It solves over twice as many instances as the state-of-the-art within set computational limits, and is up to five orders of magnitude faster.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 17 canonical work pages

  1. [1]

    Charles J. Alpert. T he ISPD98 C ircuit B enchmark S uite. In Majid Sarrafzadeh, editor, Proceedings of the 1998 International Symposium on Physical Design, ISPD 1998, Monterey, CA, USA, April 6-8, 1998 , pages 80--85, 1998. https://doi.org/10.1145/274535.274546 doi:10.1145/274535.274546

    work page arXiv 1998

  2. [2]

    T he SAT C ompetition 2014

    Anton Belov, Daniel Diepold, Marijn Heule, and Matti J\"arvisalo. T he SAT C ompetition 2014. http://www.satcompetition.org/2014/index.shtml, 2014

    work page 2014

  3. [3]

    Benson, David F

    Austin R. Benson, David F. Gleich, and Jure Leskovec. H igher-order O rganization of C omplex N etworks. CoRR , abs/1612.08447, 2016. URL: http://arxiv.org/abs/1612.08447, https://arxiv.org/abs/1612.08447 arXiv:1612.08447

    arXiv 2016

  4. [4]

    M ining H idden C ommunity in H eterogeneous S ocial N etworks

    Deng Cai, Zheng Shao, Xiaofei He, Xifeng Yan, and Jiawei Han. M ining H idden C ommunity in H eterogeneous S ocial N etworks. In Jafar Adibi, Marko Grobelnik, Dunja Mladenic, and Patrick Pantel, editors, Proceedings of the 3rd international workshop on Link discovery, LinkKDD 2005, Chicago, Illinois, USA, August 21-25, 2005 , pages 58--65, 2005. https://d...

    arXiv 2005

  5. [5]

    U mit V. C ataly \

    \" U mit V. C ataly \" u rek and Cevdet Aykanat. H ypergraph- P artitioning-based D ecomposition for P arallel S parse-matrix V ector M ultiplication. IEEE Trans. Parallel Distributed Syst. , 10(7):673--693, 1999. https://doi.org/10.1109/71.780863 doi:10.1109/71.780863

    doi:10.1109/71.780863 1999

  6. [6]

    C omputing M inimum C uts in H ypergraphs

    Chandra Chekuri and Chao Xu. C omputing M inimum C uts in H ypergraphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1085--1100, 2017. https://doi.org/10.1137/1.9781611974782.70 doi:10.1137/1.9781611974782.70

    work page doi:10.1137/1.9781611974782.70 2017

  7. [7]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. T he U niversity of F lorida S parse M atrix C ollection. ACM Trans. Math. Softw. , 38(1):1:1--1:25, 2011. https://doi.org/10.1145/2049662.2049663 doi:10.1145/2049662.2049663

    arXiv 2011

  8. [8]

    Dolan and Jorge J

    Elizabeth D. Dolan and Jorge J. Mor \' e . B enchmarking O ptimization S oftware W ith P erformance P rofiles. Math. Program. , 91(2):201--213, 2002. URL: https://doi.org/10.1007/s101070100263, https://doi.org/10.1007/S101070100263 doi:10.1007/S101070100263

    doi:10.1007/s101070100263 2002

Show all 34 references
  1. [9]

    S calable H igh-quality H ypergraph P artitioning

    Lars Gottesb \" u ren, Tobias Heuer, Nikolai Maas, Peter Sanders, and Sebastian Schlag. S calable H igh-quality H ypergraph P artitioning. ACM Trans. Algorithms , 20(1):9:1--9:54, 2024. https://doi.org/10.1145/3626527 doi:10.1145/3626527

    2024 doi

  2. [10]

    S calable S hared-memory H ypergraph P artitioning

    Lars Gottesb \" u ren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. S calable S hared-memory H ypergraph P artitioning. In Martin Farach - Colton and Sabine Storandt, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Con...

    2021 doi

  3. [11]

    Jianxiu Hao and James B. Orlin. A F aster A lgorithm for F inding the M inimum C ut in a G raph. In Greg N. Frederickson, editor, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA , pages 165--174, 1992....

    1992

  4. [12]

    A C lustering A lgorithm B ased on G raph C onnectivity

    Erez Hartuv and Ron Shamir. A C lustering A lgorithm B ased on G raph C onnectivity. Inf. Process. Lett. , 76(4-6):175--181, 2000. https://doi.org/10.1016/S0020-0190(00)00142-3 doi:10.1016/S0020-0190(00)00142-3

    doi

  5. [13]

    L abel P ropagation for H ypergraph P artitioning

    Vitali Henne. L abel P ropagation for H ypergraph P artitioning. Master's thesis, 2015. https://doi.org/10.5445/IR/1000063440 doi:10.5445/IR/1000063440

    2015

  6. [14]

    S hared-memory E xact M inimum C uts

    Monika Henzinger, Alexander Noe, and Christian Schulz. S hared-memory E xact M inimum C uts. In 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019 , pages 13--22, 2019. https://doi.org/10.1109/IPDPS.2019.0...

    2019

  7. [15]

    L ocal F low P artitioning for F aster E dge C onnectivity

    Monika Henzinger, Satish Rao, and Di Wang. L ocal F low P artitioning for F aster E dge C onnectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , ...

    2017 doi

  8. [16]

    David R. Karger. A R andomized F ully P olynomial T ime A pproximation S cheme for the A ll T erminal N etwork R eliability P roblem. In Frank Thomson Leighton and Allan Borodin, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 J...

    1995

  9. [17]

    David R. Karger. M inimum C uts in N ear-linear T ime. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 56--63, 1996. https://doi.org/10.1145/237814.237829 doi:...

    1996

  10. [18]

    Karger and Clifford Stein

    David R. Karger and Clifford Stein. A N ew A pproach to the M inimum C ut P roblem. J. ACM , 43(4):601--640, 1996. https://doi.org/10.1145/234533.234534 doi:10.1145/234533.234534

    1996

  11. [19]

    M ultilevel H ypergraph P artitioning: A pplications in VLSI D omain

    George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. M ultilevel H ypergraph P artitioning: A pplications in VLSI D omain. IEEE Trans. Very Large Scale Integr. Syst. , 7(1):69--79, 1999. https://doi.org/10.1109/92.748202 doi:10.1109/92.748202

    1999 doi

  12. [20]

    A S imple H ypergraph M in C ut A lgorithm

    Regina Klimmek and Frank Wagner. A S imple H ypergraph M in C ut A lgorithm. Technical Report B 96-02, Bericht FU Berlin Fachbereich Mathematik und Informatik, 1996. URL: http://edocs.fu-berlin.de/docs/servlets/MCRFileNodeServlet/ FUDOCS_derivate_000000000297/1996_02.pdf

    1996

  13. [21]

    Pemmaraju, and Vivek Sardeshmukh

    Kishore Kothapalli, Sriram V. Pemmaraju, and Vivek Sardeshmukh. O n the A nalysis of a L abel P ropagation A lgorithm for C ommunity D etection. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Netw...

    2013 doi

  14. [22]

    A n I mproved M in-cut A lgonthm for P artitioning V L S I N etworks

    Krishnamurthy. A n I mproved M in-cut A lgonthm for P artitioning V L S I N etworks. IEEE Transactions on Computers , C-33(5):438--446, 1984. https://doi.org/10.1109/TC.1984.1676460 doi:10.1109/TC.1984.1676460

    1984

  15. [23]

    G raph A lgorithms , pages 47--135

    Thomas Lengauer. G raph A lgorithms , pages 47--135. Vieweg+Teubner Verlag, Wiesbaden, 1990. https://doi.org/10.1007/978-3-322-92106-2_3 doi:10.1007/978-3-322-92106-2_3

    1990 doi

  16. [24]

    Wai - Kei Mak and D. F. Wong. A F ast H ypergraph M in-cut A lgorithm for C ircuit P artitioning. Integr. , 30(1):1--11, 2000. https://doi.org/10.1016/S0167-9260(00)00008-0 doi:10.1016/S0167-9260(00)00008-0

    doi

  17. [25]

    C omputing E dge-connectivity in M ultigraphs and C apacitated G raphs

    Hiroshi Nagamochi and Toshihide Ibaraki. C omputing E dge-connectivity in M ultigraphs and C apacitated G raphs. SIAM J. Discret. Math. , 5(1):54--66, 1992. https://doi.org/10.1137/0405004 doi:10.1137/0405004

    1992 doi

  18. [26]

    I mplementing an E fficient M inimum C apacity C ut A lgorithm

    Hiroshi Nagamochi, Tadashi Ono, and Toshihide Ibaraki. I mplementing an E fficient M inimum C apacity C ut A lgorithm. Math. Program. , 67:325--341, 1994. https://doi.org/10.1007/BF01582226 doi:10.1007/BF01582226

    1994 doi

  19. [27]

    Padberg and G

    M. Padberg and G. Rinaldi. A n E fficient A lgorithm for the M inimum C apacity C ut P roblem. Mathematical Programming , 47(1):19--36, May 1990. https://doi.org/10.1007/BF01580850 doi:10.1007/BF01580850

    1990 doi

  20. [28]

    A B ranch-and-cut A lgorithm for the R esolution of L arge-scale S ymmetric T raveling S alesman P roblems

    Manfred Padberg and Giovanni Rinaldi. A B ranch-and-cut A lgorithm for the R esolution of L arge-scale S ymmetric T raveling S alesman P roblems. SIAM Rev. , 33(1):60--100, 1991. https://doi.org/10.1137/1033004 doi:10.1137/1033004

    1991 doi

  21. [29]

    M inimizing S ymmetric S ubmodular F unctions

    Maurice Queyranne. M inimizing S ymmetric S ubmodular F unctions. Math. Program. , 82:3--12, 1998. https://doi.org/10.1007/BF01585863 doi:10.1007/BF01585863

    1998 doi

  22. [30]

    N ear L inear T ime A lgorithm to D etect C ommunity S tructures in L arge-scale N etworks

    Usha Nandini Raghavan, R \' e ka Albert, and Soundar Kumara. N ear L inear T ime A lgorithm to D etect C ommunity S tructures in L arge-scale N etworks. Physical Review E , 76(3), 2007. URL: https://doi.org/10.1103 https://doi.org/10.1103/physreve.76.036106 doi:10.1103/physrev...

    2007 doi

  23. [31]

    Colbourn

    Aparna Ramanathan and Charles J. Colbourn. C ounting A lmost M inimum C utsets W ith R eliability A pplications. Math. Program. , 39(3):253--261, 1987. https://doi.org/10.1007/BF02592076 doi:10.1007/BF02592076

    1987 doi

  24. [32]

    GNU P arallel: T he C ommand-line P ower T ool

    Ole Tange. GNU P arallel: T he C ommand-line P ower T ool. login Usenix Mag. , 36(1), 2011. URL: https://www.usenix.org/publications/login/february-2011-volume-36-number-1/gnu-parallel-command-line-power-tool

    2011

  25. [33]

    Alpert, Cliff C

    Natarajan Viswanathan, Charles J. Alpert, Cliff C. N. Sze, Zhuo Li, and Yaoguang Wei. T he DAC 2012 R outability-driven P lacement C ontest and B enchmark S uite. In Patrick Groeneveld, Donatella Sciuto, and Soha Hassoun, editors, The 49th Annual Design Automation Conference 2...

    2012

  26. [34]

    Wu and R

    Z. Wu and R. Leahy. A n O ptimal G raph T heoretic A pproach to D ata C lustering: T heory and I ts A pplication to I mage S egmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence , 15(11):1101--1113, 1993. https://doi.org/10.1109/34.244673 doi:10.1109/34.244673

    1993 doi

Pith tools

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