Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Shared-Memory Branch-and-Reduce for Multiterminal Cuts

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

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

Pith's one-line read This paper claims that a branch-and-reduce algorithm with new and existing reduction rules is the fastest known exact solver for multiterminal cuts, solving graphs with more than a million vertices.

desk verdict HighConnectivity reduction is load-bearing and its proof is invalid—exactness claim unproven, but the engineering and experiments deserve a serious referee. read the letter →

arxiv 1908.04141 v2 pith:4IRSLWJW submitted 2019-08-12 cs.DS cs.DC

Monika Henzinger , Alexander Noe , Christian Schulz This is my paper · ORCID
classification cs.DScs.DC
keywords multiterminalcutmultiwaybranch-and-reducekernelizationdatareductiongraphexactalgorithmintegerlinearprogramming
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

The paper tries to establish that exact minimum multiterminal cut problems, which are NP-hard for three or more terminals, can be solved in practice on far larger graphs than the standard integer-linear-programming approach allows. Its route is a branch-and-reduce algorithm wrapped around a stack of data-reduction rules: low-degree vertices are contracted, heavy edges and triangles are contracted, semi-enclosed vertices are merged into a terminal, and a new high-connectivity rule contracts edges that provably lie inside one block of some optimum. The same reductions also form a kernelization step that shrinks the graph before an ILP solves it. On the testbed the branch-and-reduce algorithm is a mean of 67 times faster than the plain ILP on instances both solve, and it solves real graphs with over a million vertices that the ILP cannot finish. If every reduction preserves at least one optimal solution, the result is a practical exact solver that replaces the ILP as the default for this problem.

What carries the argument

The engine is the branch-and-reduce loop over a queue of independent subproblems, where each subproblem is either reduced or branched on an edge incident to a terminal. Two dual operations carry the argument: contract an edge that is guaranteed not to be in at least one optimal cut, and delete (with weight bookkeeping) an edge that is guaranteed to be in every optimal cut. The new rule, HighConnectivity, uses Lemma 3: for an edge $(u,v)$, if $\lambda(u,v) + \sum_{i\in\{1,\dots,k\}\setminus\mathrm{max2}} \lambda(G,t_i,T\setminus\{t_i\})/4 > \hat{W}(G)$, then $u$ and $v$ lie in the same block of an optimal solution, so the edge is contracted; a near-linear-time lower-bound routine makes the condition checkable for every edge. The isolating cuts $\lambda(G,t_i,T\setminus\{t_i\})$ supply both the upper-bound heuristic (sum of all but the largest isolating cuts) and the lower bounds that prune branches. A shared-memory queue lets multiple threads pull independent subproblems, yielding additional parallel speedup.

What would settle it

Run the HighConnectivity rule on every small graph with, say, up to ten vertices and three or four terminals, comparing its contractions against all optimal cuts computed by brute force; any instance in which the rule contracts an edge that every optimal cut separates would invalidate Lemma 3 and collapse the exactness claim.

Watch

Extended reading notes

Core claim

The central claim is that minimum multiterminal cut admits an exact algorithm whose practical running time is no longer dominated by the ILP. The paper shows that a battery of contraction and deletion rules, most inherited from minimum-cut preprocessing and one new HighConnectivity rule, reduce the graph while guaranteeing that at least one optimal multiterminal cut survives. Whenever the connectivity lower bound of an edge plus the sum of all but the two largest isolating-cut values divided by four exceeds the current upper bound, the endpoints are in the same block of an optimal cut and the edge can be contracted. With these rules inside a branch-and-reduce search, the algorithm solves more instances to proven optimality than the ILP, and with the rules used as a kernelizer, the ILP itself becomes competitive on the reduced graph. The paper's performance claim is therefore twofold: the reductions are safe, and their engineering makes exact multiterminal cuts tractable at million-vertex scale.

Load-bearing premise

The argument stands or falls on whether the new high-connectivity contraction rule is truly safe: that whenever its test passes, the two endpoints lie in the same piece of some optimal solution.

Editorial extensions

If this is right

  • Optimal multiterminal cuts can be certified on graphs with more than a million vertices, a scale at which the plain ILP baseline never terminates.
  • The kernelized ILP inherits the same speedups when the reduced kernel is small but the cut value is large, which the experiments show on protein-protein interaction networks.
  • The branch-and-reduce variant is most efficient when the optimal cut value is small, so the two exact solvers cover complementary regimes of instance structure.
  • If the HighConnectivity reduction is safe on all graphs, the fixed-parameter tractable algorithms for multiterminal cut become deployable in practice rather than remaining purely theoretical.

Reading between the lines

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

  • As an editorial extension, the local reductions do not depend on knowing the full terminal structure, so they could be dropped into other exact frameworks, such as branch-and-cut or the FPT algorithms, to shrink any instance before deeper search.
  • The observed complementarity between cut-value-sensitive search and kernel-size-sensitive ILP points toward an adaptive hybrid that routes each subproblem to the cheaper solver; the paper does not implement this mixed dispatch.
  • The HighConnectivity inequality is stated through isolating-cut values only, so a natural testable extension is whether an analogue holds for node-weighted or directed multiway cut when a directed isolating-cut bound exists.
  • The speedups on real networks suggest that the reduction rules may also improve practical approximation algorithms, since a smaller graph with preserved optimal structure is easier for any downstream solver.
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 / 5 minor

Summary. The manuscript presents a shared-memory branch-and-reduce algorithm for the NP-hard multiterminal cut problem. It combines known and newly engineered kernelization rules (Low, High, Triangle, and a new HighConnectivity rule) with edge-branching, a priority-queue problem ordering, shared-memory parallelism, and a hybrid that first kernelizes and then solves the reduced instance with an ILP. The experimental sections report speedups of up to three orders of magnitude over a Gurobi ILP baseline, report termination with optimal solutions on graphs with more than a million vertices, and include component ablations for branching rules, queue comparators, and kernelization variants.

Significance. If the exactness guarantees were established, this would be a significant practical contribution to exact multiterminal cut solving: it would provide the first implemented parameterized-style exact solver on large graphs, with a careful experimental comparison and a clear separation of reduction and ILP components. The paper deserves credit for the breadth of experiments, the explicit evaluation of algorithmic choices, and the fact that no parameters are fitted to the reported data. However, the central exactness claim rests on Lemma 3, whose proof in Appendix A is invalid; the appendix contains inequality steps that do not follow and a false equality. Until a correct proof is supplied, the claimed exactness and the 'fastest known exact algorithm' statement are not yet substantiated.

major comments (3)
  1. [Section 4.1 and Appendix A, Claim 2] The derivation of Claim 2 from Claim 1 is invalid. Claim 1 states lambda(u,v) <= (1/4) * sum_i delta(R(t_i)) + (delta(R(u)) + delta(R(v))) / 4. Adding (1/4) * sum_i delta(R(t_i)) to both sides gives lambda(u,v) + (1/4) * sum_i delta(R(t_i)) <= (1/2) * sum_i delta(R(t_i)) + (delta(R(u)) + delta(R(v))) / 4, not the claimed bound (1/2) * sum_i delta(R(t_i)). The claimed bound is also false as stated: for k=2 with terminals s and t joined by an edge of weight 10, W=10, lambda(s,t)=10, and delta_s = delta_t = 10, so Claim 2 would require 10 + (10+10)/4 = 15 <= 10. Consequently, the safety of the HighConnectivity contraction rule, which is used in Eq. (1), is not proven.
  2. [Appendix A, proof of Lemma 3] The final equality in the proof of Lemma 3, sum_{i not in max2} delta(R(t_i)) / 2 = W(G), is false. By definition, W(G) = (1/2) * sum_{i=1}^k delta(R(t_i)) in the weighted quotient graph, since each cut edge is counted from both of its endpoint blocks. Omitting the two largest terms from the sum makes the left-hand side strictly smaller than W(G) whenever those terms are positive. Thus the displayed chain of inequalities in the proof of Lemma 3 does not establish the lemma, and the HighConnectivity reduction is not justified as written.
  3. [Sections 8.4 and 8.5] The main speedup experiments enable all kernelization rules, including HighConnectivity, and the performance claims in Section 8.5, including solving instances with more than a million vertices, are presented as exact optimal solutions. Since the only proof of HighConnectivity safety is invalid and no code or data are released, the experimental results cannot independently establish that the algorithm never returns a suboptimal cut. The abstract's claim of a fastest known exact algorithm is therefore unsubstantiated as written.
minor comments (5)
  1. [Section 4.1, Lemma 3] The notation |W(G)| is confusing because W(G) is already a numeric weight; the absolute-value bars are unexplained and should be removed.
  2. [Section 8.3] The description of the UpperBound comparator says it 'first examines problems with a lower bound'; this should presumably read 'with a lower upper bound' or a similarly explicit description.
  3. [Section 8.1.1] The phrase 'We use multiple set a instances' appears to be a typo; it should likely read 'We use multiple sets of instances'.
  4. [Figure 2 caption] The caption 'Solid line cannot be minimal as dashed line has smaller weight' is too terse; it would be clearer to state which edges are being compared and in which cases.
  5. [Section 5] The claim that in the subproblem G/e the lower bound strictly increases because the edge e was part of the largest isolating cut of the terminal s deserves a more detailed argument; as written it is not immediate that no other minimum s-T-cut can be decreased.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the load-bearing reductions are justified by external structural results and local exchange arguments, not by fitting or by self-referential definitions.

full rationale

The paper's central claims are experimental: exact branch-and-reduce and kernelized ILP outperform an ILP baseline on benchmark instances. No parameter is fitted to the reported measurements, and no computed quantity is renamed as a prediction. The reduction rules are justified by independent sources: the isolating-cut contraction is supported by Dahlhaus et al. [12]; the contraction/deletion lemmas are attributed to Cao et al. [7]; Low, HeavyEdge, HeavyTriangle, and SemiEnclosed are local exchange arguments; and the CAPFOREST connectivity lower bound is traced to Nagamochi et al. The only novel load-bearing rule, HighConnectivity, rests on Lemma 3. Its Appendix A proof contains a suspicious equality (summing δ(R(t_i))/2 over the indices excluding the two largest and claiming the result equals W(G)), and the proof of Claim 2 as written is also questionable. That is a mathematical-validity concern, not a circularity concern: the lemma is not assumed in its own proof, the rule does not define W or λ in terms of the contraction decision, and the condition is a sufficient test rather than a fitted calibration. Self-citations [20]-[23] appear for ILP adaptation and min-cut techniques, but external sources are cited alongside them ([31] for the ILP, [32,33] for CAPFOREST), so these citations are not load-bearing. Thus no step in the derivation reduces to its own inputs, and the paper should receive a non-circularity verdict even though the correctness of Lemma 3's proof should be checked separately.

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

The central claim rests on standard graph-cut theory plus a new HighConnectivity reduction whose proof is not valid. No fitted parameters or invented entities appear. The main unproven premise is the safety of the HighConnectivity contraction rule.

assumptions (4)
  • domain assumption There is a minimum multiterminal cut in which each terminal's complete isolating cut is contained in that terminal's block.
    Cites Dahlhaus et al. [12]; used to justify contracting the largest isolating cut (Section 4, 'Minimum Isolating Cuts'). This is a standard result for multiway cuts.
  • ad hoc to paper Edges with connectivity at least the current upper bound, or satisfying Lemma 3's inequality, can be contracted without changing the optimum.
    This is the HighConnectivity reduction; Lemma 3 is stated in Section 4 and its proof in Appendix A is invalid, so the safety of this contraction rule is assumed rather than established.
  • standard math The ILP formulation (Section 7) exactly models the multiterminal cut objective.
    The ILP is a standard assignment-plus-cut formulation, adapted from [20, 31], used as the baseline and in Kernel+ILP.
  • domain assumption The max-flow subroutine and CAPFOREST return correct minimum cut / connectivity bounds.
    The push-relabel algorithm and CAPFOREST are standard textbook algorithms; the paper relies on them for lower bounds and reductions (Sections 4 and 5).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Shared-Memory Branch-and-Reduce for Multiterminal Cuts." pith.science (2026). https://pith.science/paper/4IRSLWJW

@misc{pith2026190804141,
  author       = {Pith},
  title        = {Pith review of: Shared-Memory Branch-and-Reduce for Multiterminal Cuts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4IRSLWJW}},
  note         = {Machine review of arXiv:1908.04141}
}
read the original abstract

We introduce the fastest known exact algorithm~for~the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.

Figures

Figures reproduced from arXiv: 1908.04141 by the authors.

Figure 1
Figure 1. Graph with 4 terminals. Minimum s-T-cut for each terminal shown in red, C in blue 2.2 Multiterminal Cuts A multiterminal cut for k terminals T = {t1, ..., tk} is a multicut with t1 ∈ V1, ..., tk ∈ Vk. Thus, a multiterminal cut pairwisely separates all terminals from each other. The edge set of the mul￾titerminal cut with minimum weight of G is called C(G) and the associated optimal partitioning of vertices is denote… view at source ↗
Figure 2
Figure 2. Reductions. Solid line cannot be minimal as dashed line has smaller weight: (1) [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Branch on marked edge e in G, adjacent to a terminal - create two subproblems, (1) G/e and (2) G − e. w(v, t2) + P u∈V \T w(v, u) of the edges incident to v would not be part of the cut. Thus, the locally best choice is contracting v into t1. As this does not affect any other graph areas, this choice is guaranteed to be optimal. We check both HeavyEdge and SemiEnclosed in a single run labelled High. HeavyTriangle is… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Performance plots for branching edge selection variants [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Performance plots for priority queue comparator variants [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Performance plots for kernelization variants [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 8
Figure 8. Figure 8: Parallel speedup on a variety of graphs. (low-alpha dot: one graph, solid dot: average speedup) and thus, HighConnectivity is able to significantly reduce graph sizes and significantly improve running times compared to all other variants. In contrast, on the map graphs…
Figure 9
Figure 9. Figure 9: Progression of best result over time. Dot at end symbolizes that algorithm certifies [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: Speedup of Kernel+ILP to ILP 0 20 40 60 80 100 120 140 # Instances 1 10 100 1087 tIL P / t o u r [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: Speedup of avg. branch-and-reduce to ILP [PITH_FULL_IMAGE:figures/full_fig_p021_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [1]

    Andersen, F

    R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) , pages 475–486. IEEE, 2006

    work page 2006

  2. [2]

    Andersen and K

    R. Andersen and K. J. Lang. Communities from seed sets. In Proceedings of the 15th interna- tional conference on World Wide Web , pages 223–232. ACM, 2006

    work page 2006

  3. [3]

    D. A. Bader, H. Meyerhenke, P. Sanders, C. Schulz, A. Kappes, and D. Wagner. Benchmarking for graph clustering and partitioning. Encyclopedia of Social Network Analysis and Mining , pages 73–82, 2014

    work page 2014

  4. [4]

    Y. Bian, J. Ni, W. Cheng, and X. Zhang. Many heads are better than one: Local community detection by the multi-walker chain. In 2017 IEEE International Conference on Data Mining (ICDM), pages 21–30. IEEE, 2017

    work page 2017

  5. [5]

    Boldi and S

    P. Boldi and S. Vigna. The WebGraph framework I: Compression techniques. In Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004) , pages 595–601, Manhattan, USA, 2004. ACM Press

    work page 2004

  6. [6]

    Buchbinder, J

    N. Buchbinder, J. S. Naor, and R. Schwartz. Simplex partitioning via exponential clocks and the multiway cut problem. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 535–544. ACM, 2013

    work page 2013

  7. [7]

    Y. Cao, J. Chen, and J.-H. Fan. An o(1.84 k) parameterized algorithm for the multiterminal cut problem. Information Processing Letters, 114(4):167–173, 2014

    work page 2014

  8. [8]

    C. S. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. Experimental study of minimum cut algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’97) , pages 324–333. SIAM, 1997

    work page 1997

Show all 43 references
  1. [9]

    J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1–13, 2009. 17

    2009

  2. [10]

    A. Clauset. Finding local community structure in networks. Physical review E, 72(2):026132, 2005

    2005

  3. [11]

    W. H. Cunningham. The optimal multiterminal cut problem. In Reliability of computer and communication networks, pages 105–120, 1989

    1989

  4. [12]

    Dahlhaus, D

    E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing , 23(4):864–894, 1994

    1994

  5. [13]

    T. A. Davis and Y. Hu. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS) , 38(1):1, 2011

    2011

  6. [14]

    L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8(3):399–404, 1956

    1956

  7. [15]

    L. R. Ford Jr and D. R. Fulkerson. Flows in networks . Princeton university press, 2015

    2015

  8. [16]

    Funke, S

    D. Funke, S. Lamm, P. Sanders, C. Schulz, D. Strash, and M. von Looz. Communication-free massively distributed graph generation. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 336–347. IEEE, 2018

    2018

  9. [17]

    H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences , 30(2):209–221, 1985

    1985

  10. [18]

    A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921–940, 1988

    1988

  11. [19]

    Harris and F

    T. Harris and F. Ross. Fundamentals of a method for evaluating rail net capacities. Technical report, RAND CORP SANTA MONICA CA, 1955

    1955

  12. [20]

    Henzinger, A

    A. Henzinger, A. Noe, and C. Schulz. ILP-based Local Search for Graph Partitioning. Pro- ceedings of the 17th International Symposium on Experimental Algorithms (SEA 2018) , 2018

    2018

  13. [21]

    Henzinger, A

    M. Henzinger, A. Noe, and C. Schulz. Shared-memory Exact Minimum Cuts. Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) , 2019

    2019

  14. [22]

    Henzinger, A

    M. Henzinger, A. Noe, C. Schulz, and D. Strash. Practical minimum cut algorithms. In 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 48–61. SIAM, 2018

    2018

  15. [23]

    Henzinger, S

    M. Henzinger, S. Rao, and D. Wang. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1919–

    1919

  16. [24]

    Karaoz, T

    U. Karaoz, T. Murali, S. Letovsky, Y. Zheng, C. Ding, C. R. Cantor, and S. Kasif. Whole- genome annotation by using evidence integration in functional-linkage networks. Proceedings of the National Academy of Sciences , 101(9):2888–2893, 2004

    2004

  17. [25]

    I. M. Kloumann and J. M. Kleinberg. Community membership identification from small seed sets. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discov- ery and data mining , pages 1366–1375. ACM, 2014. 18

    2014

  18. [26]

    Leskovec, K

    J. Leskovec, K. J. Lang, and M. Mahoney. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th international conference on World wide web , pages 631–640. ACM, 2010

    2010

  19. [27]

    F. Luo, J. Z. Wang, and E. Promislow. Exploring local community structures in large networks. Web Intelligence and Agent Systems: An International Journal , 6(4):387–400, 2008

    2008

  20. [28]

    S. A. Macskassy and F. Provost. A simple relational classifier. Technical report, NEW YORK UNIV NY STERN SCHOOL OF BUSINESS, 2003

    2003

  21. [29]

    D. Marx. Parameterized graph separation problems. Theoretical Computer Science , 351(3):394–406, 2006

    2006

  22. [30]

    Mislove, B

    A. Mislove, B. Viswanath, K. P. Gummadi, and P. Druschel. You are who you know: inferring user profiles in online social networks. In Proceedings of the third ACM international conference on Web search and data mining , pages 251–260. ACM, 2010

    2010

  23. [31]

    Nabieva, K

    E. Nabieva, K. Jim, A. Agarwal, B. Chazelle, and M. Singh. Whole-proteome predic- tion of protein function via graph-theoretic analysis of interaction maps. Bioinformatics, 21(suppl 1):i302–i310, 2005

    2005

  24. [32]

    Nagamochi and T

    H. Nagamochi and T. Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics , 5(1):54–66, 1992

    1992

  25. [33]

    Nagamochi, T

    H. Nagamochi, T. Ono, and T. Ibaraki. Implementing an efficient minimum capacity cut algorithm. Mathematical Programming, 67(1):325–341, 1994

    1994

  26. [34]

    Padberg and G

    M. Padberg and G. Rinaldi. An efficient algorithm for the minimum capacity cut problem. Mathematical Programming, 47(1):19–36, 1990

    1990

  27. [35]

    L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999

    1999

  28. [36]

    Pferschy, R

    U. Pferschy, R. Rudolf, and G. J. Woeginger. Some geometric clustering problems. Nord. J. Comput., 1(2):246–263, 1994

    1994

  29. [37]

    A. J. Soper, C. Walshaw, and M. Cross. A combined evolutionary search and multilevel optimisation approach to graph-partitioning. Journal of Global Optimization , 29(2):225–241, 2004

    2004

  30. [38]

    H. S. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Software Eng., 3(1):85–93, 1977

    1977

  31. [39]

    Szklarczyk, A

    D. Szklarczyk, A. Franceschini, M. Kuhn, M. Simonovic, A. Roth, P. Minguez, T. Doerks, M. Stark, J. Muller, P. Bork, et al. The string database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic acids research , 39(suppl 1):D561–D568, 2010

    2011

  32. [40]

    Szklarczyk, A

    D. Szklarczyk, A. L. Gable, D. Lyon, A. Junge, S. Wyder, J. Huerta-Cepas, M. Simonovic, N. T. Doncheva, J. H. Morris, P. Bork, et al. String v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets....

    2018

  33. [41]

    Vazquez, A

    A. Vazquez, A. Flammini, A. Maritan, and A. Vespignani. Global protein function prediction from protein-protein interaction networks. Nature biotechnology, 21(6):697, 2003

    2003

  34. [42]

    M. Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory of Computing Systems, 46(4):723–736, 2010

    2010

  35. [43]

    W. Ye, L. Zhou, D. Mautz, C. Plant, and C. B¨ ohm. Learning from labeled and unlabeled vertices in networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 1265–1274. ACM, 2017. A Proofs In order to prove Lemma 3 w...

    2017

Pith tools

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