Pith. sign in

REVIEW 3 major objections 3 minor 44 references

On the non-submodularity of the problem of adding links to minimize the effective graph resistance

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

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

Pith's one-line read The paper constructs a graph family on 2N nodes for which the submodularity ratio of normalized effective graph resistance tends to zero, so greedy link addition has no guaranteed approximation quality.

desk verdict The claimed gamma->0 result is not supported by the paper's own equations: dividing Eq. (6) by Eq. (7) gives a ratio tending to 6, not 0, and the appendix has sign errors under the main proof. read the letter →

arxiv 2501.03363 v1 pith:M2D6NKBO submitted 2025-01-06 cs.DS math-phmath.MP

Massimo A. Achterberg , Robert E. Kooij This is my paper · ORCID
classification cs.DSmath-phmath.MP MSC 05C8205C5090C2768R10
keywords effectivegraphresistanceKirchhoffindexnetworkaugmentationsubmodularityratiogeneralizedgreedyalgorithmk-GRIProbustness
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 the problem of choosing k links to minimize effective graph resistance, already known to be NP-hard, is not merely non-submodular but fails generalized submodularity in a way that destroys the standard greedy performance guarantees. It builds a family of graphs on 2N nodes where the submodularity ratio gamma is at most roughly 6/N, hence approaches zero; at gamma equal to zero, known bounds only say the greedy solution is nonnegative, which is no guarantee at all. The same family shows that the greedy algorithm can be suboptimal, and exhaustive and random experiments on small graphs find an efficiency as low as 0.878 already for N=10 and k=3. A reader should care because greedy is the practical method for this NP-hard augmentation problem, and the result shows its worst-case behavior is not controlled by submodularity-based theory.

What carries the argument

The central object is the submodularity ratio gamma, the largest constant such that the marginal gain of adding an element v to a small set S is at least gamma times the marginal gain of adding v to a larger set R. For f equal to the normalized effective graph resistance r_G, the paper computes the ratio of two marginal gains for one specific triple (S empty, v, R) on a family of graphs. The computation is carried by electrical-network reductions: Theorem 11 of the cited resistance-distance paper gives the change in effective graph resistance under an edge-weight change, and series, parallel, and $\Delta$-Y transformations on the planar augmented graph produce closed forms for the resistances omega_ij, omega_ik, and omega_jk. The identity doing the work is the exact quotient of the two resistance differences in Theorem 8, which yields the upper bound on gamma.

What would settle it

Compute the four effective graph resistances in Theorem 8 for N=6 directly from the Laplacian eigenvalues using R_G = N * sum_{i=2}^N 1/mu_i, and form the ratio of the two gains. If the ratio does not match the right-hand side of Eq. (8), or if for larger even N the ratio does not tend to zero, the claimed collapse of the greedy guarantee is not established.

Watch

Extended reading notes

Core claim

The central claim is that k-GRIP for the normalized effective graph resistance is not generalized submodular. For the graph formed by taking a complete bipartite graph K_{2,N-2}, choosing nodes i and j in the two-node part, and attaching a path of length N/2 to each of two selected nodes in the other part, the paper proves, with S empty, v equal to the edge (i,j), and R the two edges that connect the far ends of the paths back to i and j, that the gain from adding v alone is 4/(N-2) while the gain from adding v after R is 2(N+3)(N+4)(N+5)/(3(N+1)(N+2)($N^{2}$+N-4)). The quotient of these gains gives an upper bound gamma <= 6(N+1)(N+2)($N^{2}$+N-4)/[(N-2)N(N+3)(N+4)(N+5)] ~ 6/N, which tends to zero. Since the performance bounds in the paper depend directly on gamma, a gamma arbitrarily close to zero implies that the greedy algorithm's solution quality cannot be guaranteed. The paper additionally reports small-graph experiments where the greedy efficiency eta = R_G(optimal)/R_G(greedy) reaches a minimum of 0.878 for N=10 and k=3.

Load-bearing premise

The upper bound on gamma rests on the closed-form effective-resistance formulas in the appendix being correct; the printed derivation of one intermediate resistance contains sign inconsistencies, so the conclusion holds only if the corrected algebra reproduces those formulas.

Editorial extensions

If this is right

  • For k-GRIP with effective graph resistance, the greedy algorithm has no guaranteed approximation ratio derived from submodularity or generalized submodularity; only problem-specific bounds could apply.
  • As the constructed graph family grows, gamma becomes arbitrarily small, so the practical heuristic's worst-case performance is not controlled by the existing gamma-dependent bounds.
  • The small-graph experiments show that greedy solutions are already suboptimal at modest sizes, so exact methods or alternative heuristics may be needed when solution quality matters.
  • Any future guarantee for greedy link addition must exploit structure beyond set-function submodularity, such as spectral properties of the Laplacian or electrical-network structure.
  • The efficiency value 0.878 provides a concrete benchmark: any proposed improvement to the greedy rule must be tested against this known worst case for N=10 and k=3.

Reading between the lines

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

  • The same counterexample construction could plausibly transfer to other Laplacian-spectrum-based robustness metrics, since the added edge (i,j) has a small effect on the original graph but a large effect after the set R is present; testing gamma for algebraic connectivity or spanning-tree counts would be a direct extension.
  • A natural next step is to scale up the N=10 worst-case graph to see whether the greedy efficiency eta continues to drop; the gamma-to-zero family suggests arbitrarily bad greedy behavior may be constructible, though the paper does not prove it.
  • Even though worst-case guarantees vanish, average-case or instance-specific performance may still be acceptable; the paper's experiments do not rule that out, so a distributional analysis of greedy errors would be a useful test.
  • The paper's counterexample uses only one triple (S empty, v, R) to bound gamma, so computing the exact gamma for larger instances might reveal even stronger non-submodularity, which would further narrow the space of possible guarantees.
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 / 3 minor

Summary. The paper studies the k-GRIP problem of adding links to minimize effective graph resistance. It claims that for a family of graphs on 2N nodes, the submodularity ratio γ of the normalized effective graph resistance is upper-bounded by a quantity of order 6/N, so γ tends to 0 and the known greedy performance guarantees for generalized submodular functions give no bound. The paper also reports exhaustive and sampled experiments for small graphs, finding greedy solutions with efficiency as low as 0.878. The central theoretical claim rests on Theorem 8, which computes two resistance differences algebraically, and Theorem 9, which combines them into a bound on γ.

Significance. If correct, the result would be a useful strengthening of the known non-submodularity of the k-GRIP objective: it would show that γ-based performance guarantees degrade to zero on a natural graph family. The paper is transparent in giving explicit algebraic expressions and a checkable construction, and the small-graph brute-force comparison is a reasonable empirical contribution. However, the main theorem is invalid as stated: the quotient obtained from the paper's own Eqs. (6) and (7) tends to 6, not 0, so the construction does not establish γ→0. The central claim is therefore unsupported, and the paper would need a substantially different construction or a corrected analysis to make its stated contribution.

major comments (3)
  1. [Theorem 9 and Eq. (8)] The upper bound in Eq. (8) does not follow from Theorem 8. Substituting Eq. (6) and Eq. (7) into the ratio that bounds γ gives 6(N+1)(N+2)(N^2+N-4) / ((N-2)(N+3)(N+4)(N+5)), which tends to 6 as N grows, not to 0. Eq. (8) contains an extra factor N in the denominator. For the displayed graph with N=6, this ratio is about 3.22, so it imposes no constraint on γ, which is at most 1. Thus the family of graphs in Fig. 2 does not establish γ→0, and the paper's headline claim is not supported.
  2. [Appendix A, expression for ω_jk] The printed formula for ω_jk below Fig. 14 yields a negative effective resistance for admissible parameters, for example N=6, k=1 gives approximately -1.05, which is impossible for a resistance. The formula is also inconsistent with the subsequently claimed difference ω_ik - ω_jk = 2(2k-N-3)/(N^2+N-4); substituting N=6, k=1 into the two printed expressions gives a different value. Since this difference is used to derive Eq. (19) and hence Eq. (7), the proof of Theorem 8 must be redone before Eq. (7) can be accepted.
  3. [Eq. (3) and surrounding text] As printed, Eq. (3) uses the path-graph resistance value (N-1 choose 3), but the Kirchhoff index of the path graph P_N is (N^3-N)/6 = (N+1 choose 3). With the printed constant, the denominator of Eq. (3) vanishes for N=5 and the normalized resistance is not bounded between 0 and 1. This normalization is used throughout the paper; it should be corrected, even though the ratio argument is unaffected by the linear rescaling.
minor comments (3)
  1. [Algorithm 1, lines 3 and 8] The algorithm initializes r_G,opt to +∞ and then updates only when r_G(G_i ∪ W_j) > r_G,opt; since no finite value exceeds ∞, the algorithm never selects a link. The sentinel should be -∞ for a maximization problem. Line 12 also uses the undefined variable Vopt instead of Wopt.
  2. [Table 1 and Section 5] The caption calls the N=9 and N=10 entries 'lower bounds', but if those values were obtained from a random subset of graphs, the reported minimum efficiency over the sample is an upper bound on the true minimum, not a lower bound. In addition, the text says only N≤8 graphs were checked exhaustively while the table header lists exact counts for N=9 and N=10; the distinction between exhaustive and sampled results should be stated clearly.
  3. [Notation and typos] There are several small presentation issues: the normalization constant in Eq. (3) appears to be a typo for (N+1 choose 3); the phrase 'for all k ≤ i' in the proof of Eq. (6) should presumably read 'for all k ≠ i,j'; and the variable name Vopt in Algorithm 1 should be Wopt.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the submodularity-ratio bound is derived from exact effective-resistance computations, not from fitted inputs or self-referential definitions.

full rationale

The paper's central claim is that there exists a family of graphs for which the submodularity ratio gamma of the normalized effective graph resistance tends to zero. The derivation chain is: define the family in Fig. 2, choose a particular link v and set R, compute the two exact resistance differences RG(G)-RG(G union {v}) and RG(G union R)-RG(G union R union {v}) via series, parallel, and Y-delta reductions in Appendix A, and then form the ratio. Under Definition 5, a single valid triple S, R, v gives an upper bound on gamma, so taking the ratio of Eq. (6) to Eq. (7) is not circular: it is the standard use of a witness inequality to bound a global constant. The normalization in Eq. (3) cancels exactly from the ratio, and the paper states this cancellation explicitly in the proof of Theorem 9. No parameter is fitted to data and later called a prediction; no post-hoc exclusions are used; no result is imported from a same-author uniqueness theorem or ansatz. The only self-citation that is at all load-adjacent is the NP-hardness reference [19] by the same authors, but that result is not used to derive the gamma bound and is independently established elsewhere in the literature. The known non-submodularity example from [34] is used only as motivation and is not part of the gamma-to-zero construction. The skeptic's objection that Theorem 9's displayed bound does not algebraically follow from Eqs. (6)-(7), and the reader's note that the printed Appendix contains sign errors, are serious correctness concerns about the proof, not circularity: a miscalculated ratio is still a computed quantity, not an input disguised as an output. Because no step satisfies the required test of reducing to its own inputs by construction, the honest finding is no significant circularity, score 0.

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

The central claim depends only on standard circuit-theoretic identities and the specific graph construction. No free parameters are fitted. No new entities are introduced.

assumptions (3)
  • standard math Theorem 11 of [40] (Yang-Klein formula for change in effective graph resistance under edge weight perturbation)
    Used at the start of Appendix A to express RG(G) - RG(G union {v}) and RG(G union R) - RG(G union R union {v}) as sums over resistance differences.
  • standard math Upper and lower bounds on effective graph resistance for connected graphs, (N-1)/3 and N-1, used in the normalization Eq. (3)
    These bounds are quoted from [15] and are needed only to normalize r_G; the gamma computation is invariant to the normalization.
  • domain assumption Planarity of the graph G union R and the validity of series, parallel, and Y-delta transformations for effective resistance
    Used throughout Appendix A.2 to reduce the resistance network to a few effective resistances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the non-submodularity of the problem of adding links to minimize the effective graph resistance." pith.science (2026). https://pith.science/paper/M2D6NKBO

@misc{pith2026250103363,
  author       = {Pith},
  title        = {Pith review of: On the non-submodularity of the problem of adding links to minimize the effective graph resistance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M2D6NKBO}},
  note         = {Machine review of arXiv:2501.03363}
}
abstract

We consider the optimisation problem of adding $k$ links to a given network, such that the resulting effective graph resistance is as small as possible. The problem was recently proven to be NP-hard, such that optimal solutions obtained with brute-force methods require exponentially many computation steps and thus are infeasible for any graph of realistic size. Therefore, it is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed. However, it is known that the optimisation problem we are facing, is not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio $\gamma$. A performance bound, which is a function of $\gamma$, also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed. Furthermore, we show that the greedy algorithm does not always yield the optimal solution and demonstrate that even for a small graph with 10 nodes, the ratio between the optimal and the greedy solution can be as small as 0.878.

Figures

Figures reproduced from arXiv: 2501.03363 by the authors.

Figure 1
Figure 1. The smallest counterexample showing that the normalized effective graph resistance [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. The graph G consisting of 2N nodes; two path graphs with N/2 nodes are attached to a complete bipartite graph K2,N−2 on N nodes. The element v is the dashed green link in the complete bipartite graph between node i and j. The set R, represented by dotted red links, is the union of the link connecting node i with the left-most node of the graph and the link connecting node j with the right-most node of the graph. In … view at source ↗
Figure 3
Figure 3. The upper bound for the submodularity ratio [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: The graph G with the currently known smallest efficiency ηmin = 0.878 on N = 10 nodes and the k = 3 added links are shown as dashed green links. 6 Conclusion We consider the optimisation problem of adding k links to a given network, such that the resulting normalized e…
Figure 5
Figure 5. Figure 5: The original graph G. The element v is the dashed green link between node i and j. We directly apply Theorem 11 with δ = 1 and N˜ = 2N, where the graph G is considered the “original graph” and graph G′ is graph G augmented with v. Then we find RG(G) − RG(G ∪ {v}) = 2N …
Figure 6
Figure 6. Figure 6: The augmented graph G ∪ R, which contains the original graph G and the set R, denoted by dotted red links. We now return to Theorem 11 with δ = 1 and N˜ = 2N, where the graph G ∪ R is considered the “original graph”. Then we find RG(G ∪ R) − RG(G ∪ R ∪ {v}) = 2N P2N k=…
Figure 7
Figure 7. Figure 7: The graph G ∪ R redrawn as a planar graph. Because G ∪ R is planar, according to [36], it is possible to determine the effective resistance for each node pair by a sequence of series, parallel, Y − ∆, and ∆ − Y transformations. 17 [PITH_FULL_IMAGE:figures/full_fig_p01…
Figure 8
Figure 8. Figure 8: Result of simplification step 1 on the graph [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: Result of simplification step 2 on the graph [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 10
Figure 10. Figure 10: Result of simplification step 3 on the graph [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 11
Figure 11. Figure 11: Result of simplification step 4 on the graph [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]
Figure 12
Figure 12. Figure 12: Result of simplification step 5a on the graph [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: Result of simplification step 5b on the graph [PITH_FULL_IMAGE:figures/full_fig_p020_13.png]
Figure 14
Figure 14. Figure 14: Result of simplification step 5c on the graph [PITH_FULL_IMAGE:figures/full_fig_p021_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 32 canonical work pages

  1. [1]

    J. S. Baras and P. Hovareshti. Efficient and robust communication topologies for distributed decision making in networked systems. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference , pages 3751–3756,

    work page 2009

  2. [2]

    A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximiza- tion of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning - Volume 70 , ICML’17, pages 498––507. JMLR.org, 2017. URL https://arxiv.org/pdf/1703.02100.pdf

    work page Pith review arXiv 2017

  3. [3]

    Cetinay, C

    H. Cetinay, C. Mas-Machuca, J. L. Marzo, R. Kooij, and P. Van Mieghem. Comparing Destructive Strategies for Attacking Networks. In J. Rak and D. Hutchison, editors, Guide to Disaster- Resilient Communication Networks, pages 117–140. Springer International Publishing, 2020. doi: 10.1007/978-3-030-44685-7_5

    work page doi:10.1007/978-3-030-44685-7_5 2020

  4. [4]

    P. H. Chan, L. C. Lau, A. Schild, S. C. Wong, and H. Zhou. Network Design for S-t Effective Resistance. ACM Trans. Algorithms, 18(3), Oct 2022. doi:10.1145/3522588

    work page doi:10.1145/3522588 2022

  5. [5]

    Submodularity in Input Node Selection for Networked Systems

    A. Clark, B. Alomair, L. Bushnell, and R. Poovendran. Submodularity in Input Node Selection for Networked Linear Systems: Efficient Algorithms for Performance and Controllability. IEEE Control Systems Magazine, 37(6):52–74, 2017. URL https://arxiv.org/abs/1605.09465. doi: 10.1109/MCS.2017.2743518

    work page Pith review arXiv 2017

  6. [6]

    Clark, L

    A. Clark, L. Bushnell, and R. Poovendran. A Supermodular Optimization Framework for Leader Selection Under Link Noise in Linear Multi-Agent Systems. IEEE Transactions on Automatic Control, 59(2):283–296, 2014. URL https://ieeexplore.ieee.org/document/6595543. doi: 10.1109/TAC.2013.2281473

    work page arXiv 2014

  7. [7]

    Clark, Q

    A. Clark, Q. Hou, L. Bushnell, and R. Poovendran. A submodular optimization approach to leader-follower consensus in networks with negative edges. In 2017 American Control Conference (ACC), pages 1346–1352, 2017. URL https://ieeexplore.ieee.org/document/7963139. doi: 10.23919/ACC.2017.7963139

    work page arXiv 2017

  8. [8]

    Clark and R

    A. Clark and R. Poovendran. A submodular optimization framework for leader selection in linear multi-agent systems. In 2011 50th IEEE Conference on Decision and Control and European Con- trol Conference, pages 3614–3621, 2011. URL https://labs.ece.uw.edu/nsl/papers/CDC-11. pdf. doi:10.1109/CDC.2011.6160248

    work page arXiv 2011

Show all 44 references
  1. [9]

    G. P. Clemente and A. Cornaro. Bounding robustness in complex networks under topo- logical changes through majorization techniques. Eur. Phys. J. B , 93(114):1–12, 2020. URL: https://link.springer.com/article/10.1140/epjb/e2020-100563-2, doi:10.1140/ epjb/e2020-100563-2. 12

    2020 doi

  2. [10]

    Das and D

    A. Das and D. Kempe. Submodular Meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. In Proceedings of the 28th International Confer- ence on International Conference on Machine Learning , ICML’11, pages 1057—-1064, Madison, WI...

    2011 arXiv

  3. [11]

    Ellens, F

    W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, and R. E. Kooij. Effective graph resistance. Linear Algebra and its Applications , 435(10):2491–2506, 2011. Special Issue in Honor of Dragos Cvetkovic. URL: https://www.sciencedirect.com/science/article/pii/ S00243795110...

    2011 doi

  4. [12]

    S. R. Etesami. Consensus under Network Interruption and Effective Resistance Interdiction. In 2021 American Control Conference (ACC) , pages 814–819, 2021. doi:10.23919/ACC50511. 2021.9483395

    2021

  5. [13]

    M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal , 23:298 – 305,

  6. [15]

    Ghosh, S

    A. Ghosh, S. Boyd, and A. Saberi. Minimizing Effective Resistance of a Graph. SIAM Review, 50(1):37–66, 2008. doi:10.1137/050645452

    2008 doi

  7. [16]

    Z. He. Performance of complex networks . Phd., Delft University of Technology, Mar 2020

    2020

  8. [17]

    W. Jun, M. Barahona, T. Yue-Jin, and D. Hong-Zhong. Natural connectivity of complex net- works. Chinese Physics Letters , 27(7):078902, jul 2010. URL: https://dx.doi.org/10.1088/ 0256-307X/27/7/078902, doi:10.1088/0256-307X/27/7/078902

    2010 doi

  9. [18]

    D. J. Klein and M. Randi´ c. Resistance distance. Journal of Mathematical Chemistry , 12:81– 95, 1993. URL: https://link.springer.com/article/10.1007/BF01164627, doi:10.1007/ BF01164627

    1993 doi

  10. [19]

    R. E. Kooij and M. A. Achterberg. Minimizing the effective graph resistance by adding links is NP- hard. Operations Research Letters, 51(6):601–604, 2023. URL: https://www.sciencedirect. com/science/article/pii/S0167637723001669, doi:10.1016/j.orl.2023.10.002

    2023 doi

  11. [20]

    G. Li, Z. F. Hao, H. Huang, and H. Wei. Maximizing Algebraic Connectivity via Minimum Degree and Maximum Distance. IEEE Access, 6:41249–41255, 2018. doi:10.1109/ACCESS. 2018.2857411

    2018

  12. [21]

    Z. Liu, J. Jin, H. Chang, D. Du, and X. Zhang. Improved algorithms for non-submodular function maximization problem. Theoretical Computer Science, 931:49–55, 2022. URL: https: //www.sciencedirect.com/science/article/pii/S0304397522004510, doi:10.1016/j.tcs. 2022.07.029. 13

    2022 doi

  13. [22]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94–112, 2014. doi:10.1016/j.jsc.2013.09.003

    2014 doi

  14. [23]

    Mosk-Aoyama

    D. Mosk-Aoyama. Maximum algebraic connectivity augmentation is NP-hard. Operations Research Letters , 36(6):677–679, 2008. URL: https://www.sciencedirect.com/science/ article/pii/S0167637708001077, doi:10.1016/j.orl.2008.09.001

    2008 doi

  15. [24]

    G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions – I. Mathematical Programming, 14:265–294, 1978. URL https:// www.cs.toronto.edu/~eidan/papers/submod-max.pdf. URL: https://www.cs.toronto.edu/ ~eidan/papers/...

    1978 doi

  16. [25]

    Papagelis

    M. Papagelis. Refining Social Graph Connectivity via Shortcut Edge Addition. ACM Trans. Knowl. Discov. Data , 10(2), oct 2015. URL https://dl.acm.org/doi/pdf/10.1145/2757281. doi:10.1145/2757281

    2015 doi

  17. [26]

    Pizzuti and A

    C. Pizzuti and A. Socievole. A Genetic Algorithm for Improving Robustness of Complex Networks. In 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI) , pages 514–521, 2018. doi:10.1109/ICTAI.2018.00085

    2018

  18. [27]

    Pizzuti and A

    C. Pizzuti and A. Socievole. A genetic algorithm for enhancing the robustness of complex networks through link protection. In International Conference on Complex Networks and their Applications, pages 807–819. Springer, 2018

    2018

  19. [28]

    Predari, R

    M. Predari, R. Kooij, and H. Meyerhenke. Faster Greedy Optimization of Resistance-based Graph Robustness. In 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) , pages 1–8, Los Alamitos, CA, USA, Nov 2022. IEEE Com- puter Society...

    2022

  20. [29]

    D. F. Rueda, E. Calle, and J. L. Marzo. Robustness comparison of 15 real telecommunication networks: Structural and centrality measurements. Journal of Network and Systems Management, 25(2):269–289, Apr 2017. doi:10.1007/s10922-016-9391-y

    2017 doi

  21. [30]

    Santiago and Y

    R. Santiago and Y. Yoshida. Weakly Submodular Function Maximization Using Local Submod- ularity Ratio, 2020. URL https://arxiv.org/pdf/2004.14650.pdf. doi:10.48550/ARXIV. 2004.14650

    2020 doi arXiv

  22. [31]

    C. M. Schneider, A. A. Moreira, J. S. Andrade, S. Havlin, and H. J. Herrmann. Mitigation of malicious attacks on networks. Proceedings of the National Academy of Sciences , 108(10):3838– 3841, 2011. URL: https://www.pnas.org/doi/abs/10.1073/pnas.1009440108, arXiv:https: //www....

    2011 doi

  23. [32]

    L. Shan, Y. Yi, and Z. Zhang. Improving Information Centrality of a Node in Complex Net- works by Adding Edges. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18 , pages 3535–3541. International Joint Conferences on Artifi...

    2018 doi

  24. [33]

    Summers and M

    T. Summers and M. Kamgarpour. Performance guarantees for greedy maximization of non- submodular controllability metrics. In 2019 18th European Control Conference (ECC) , pages 2796–2801, 2019. URL https://ieeexplore.ieee.org/document/8795800. doi:10.23919/ ECC.2019.8795800

    2019

  25. [34]

    Topology design for optimal network coherence

    T. Summers, I. Shames, J. Lygeros, and F. Dorfler. Correction to “Topology design for optimal network coherence”, 2017. URL https://personal.utdallas.edu/~ths150130/papers/ECC_ Correction.pdf

    2017

  26. [35]

    Summers, I

    T. Summers, I. Shames, J. Lygeros, and F. D¨ orfler. Topology design for optimal network co- herence. In 2015 European Control Conference (ECC) , pages 575–580, 2015. URL https: //personal.utdallas.edu/~ths150130/papers/NetworkCoherence.pdf. doi:10.1109/ECC. 2015.7330605

    2015

  27. [36]

    Truemper

    K. Truemper. On the delta-wye reduction for planar graphs. J. Graph Theory , 13(2):141–148,

  28. [37]

    Van Mieghem, D

    P. Van Mieghem, D. Stevanovi´ c, F. Kuipers, C. Li, R. van de Bovenkamp, D. Liu, and H. Wang. Decreasing the spectral radius of a graph by link removals. Phys. Rev. E , 84:016101, Jul 2011. URL https://www.nas.ewi.tudelft.nl/people/Piet/papers/PhysRevE2011_ decreasing_largest_...

    2011 doi

  29. [38]

    Wang and P

    H. Wang and P. Van Mieghem. Algebraic Connectivity Optimization via Link Addition. In Proceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information and Computing Sytems , BIONETICS ’08, Brussels, BEL, 2008. ICST (Institute for Computer Sciences...

    2008

  30. [39]

    X. Wang, E. Pournaras, R. E. Kooij, and P. Van Mieghem. Improving robust- ness of complex networks via the effective graph resistance. The European Physi- cal Journal B , 87(221), 2014. URL https://nas.ewi.tudelft.nl/people/Piet/papers/ EPJb2014_ImprovingRobustnessviaEffective...

    2014 doi

  31. [40]

    original graph

    Y. Yang and D. J. Klein. A recursion formula for resistance distances and its applications. Discrete Applied Mathematics , 161(16):2702–2715, 2013. URL: https://www.sciencedirect. com/science/article/pii/S0166218X12002806, doi:10.1016/j.dam.2012.07.015. A Proof of Theorem 8 Pr...

    2013 doi

  32. [45]

    Hence, A consists of N − 4 nodes

    Then we define the node set A as the nodes in K2,N −2 minus the nodes i, j, l and m. Hence, A consists of N − 4 nodes. Next, the subset of nodes B is formed by the nodes in the two path graphs plus the nodes l and m. Therefore, set B contains N + 2 nodes. We can now split up t...

  33. [1973]

    URL: http://dml.cz/dmlcz/101168

  34. [1989]

    1002/jgt.3190130202

    URL: http://dblp.uni-trier.de/db/journals/jgt/jgt13.html#Truemper89, doi:10. 1002/jgt.3190130202

  35. [2009]

    doi:10.1109/CDC.2009.5400448

    2009

  36. [2022]

    doi:10.1109/TKDE.2022.3163672

    2022

Pith tools

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