pith. sign in

arxiv: 2605.27998 · v1 · pith:2UDHCBFQnew · submitted 2026-05-27 · 💻 cs.DS · cs.DM

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs

Ali Abbasi , Eli Friedman , Leana Golubchik , Samir Khuller , Marco Paolieri This is my paper

Pith reviewed 2026-06-29 09:55 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords r-edge interdiction coveringdynamic programming on treesbounded treewidthnetwork interdictionfacility interdictionsmall set bipartite vertex expansionNP-completeness
0
0 comments X

The pith

An O(n r^2) dynamic programming algorithm solves the r-edge interdiction covering problem on trees.

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

The paper gives a dynamic programming procedure that computes an optimal set of at most r edges to remove from a tree so that the total weight of customers disconnected from every facility is maximized. The procedure runs in O(n r^2) time and is therefore linear in the number of nodes once r is treated as a fixed parameter. The same recurrence works on graphs of bounded treewidth and yields an identical runtime bound. A related problem in which up to r facilities rather than edges may be removed admits the same O(n r^2) bound on trees and immediately supplies an O(n^3) algorithm for the small-set bipartite vertex expansion problem restricted to trees.

Core claim

REIC on trees can be solved by a bottom-up dynamic program that, for each subtree, records the best covering value obtainable for every possible number of interdictions used and every possible status of the subtree root with respect to the nearest remaining facility. The same table-filling approach extends without change to bounded-treewidth graphs and to the facility-removal variant RFIC on trees.

What carries the argument

A dynamic programming table indexed by subtree, number of interdictions used, and connection status of the subtree root to the nearest surviving facility.

If this is right

  • REIC is solvable in time linear in n for any fixed r on trees.
  • The same linear dependence on n holds for every graph whose treewidth is bounded by a constant.
  • RFIC on trees is solvable in O(n r^2) time even though the problem is NP-complete on general graphs.
  • SSBVE on trees is solvable in O(n^3) time via the RFIC reduction.

Where Pith is reading between the lines

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

  • The same table structure may be reusable for other interdiction objectives that depend on disconnection from a designated set of terminals.
  • Because the algorithm is fixed-parameter linear in n, it becomes practical for very large trees once r is modest.
  • The O(n^3) bound for SSBVE on trees suggests that similar expansion problems may admit efficient tree algorithms even when they remain hard on general graphs.

Load-bearing premise

The input graph must be a tree or have bounded treewidth so that the dynamic-programming recurrence can be evaluated in the stated time.

What would settle it

A tree on which the dynamic program returns a strictly suboptimal covering value for some choice of r, or a sequence of trees whose measured running times grow faster than linear in n for fixed r.

Figures

Figures reproduced from arXiv: 2605.27998 by Ali Abbasi, Eli Friedman, Leana Golubchik, Marco Paolieri, Samir Khuller.

Figure 1
Figure 1. Figure 1: Each case is XY value for node v under a different interdiction example on the same graph; customers are circles; facilities are squares; facilities reachable from v are shaded in blue. 2.1 Base Case: Leaves We start by defining values VXY (v, b) for when v is a leaf of the tree with parent w. • For a facility leaf node v ∈ S, regardless of whether a facility can be reached through w (i.e., for both X = 0 … view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of average mean runtime under varying experimental settings. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of sensitivity to different variables: (a) coefficient of variation as a function [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the source of high variance in FR runtime: (a) runtime box plot for different [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
read the original abstract

Given a graph $G$ of $n$ nodes partitioned into facilities and customers, the $r$-edge interdiction covering problem (REIC) is to remove up to $r$ edges so as to maximize the total weight of customers disconnected from all facilities, which is called the covering objective function. While REIC is known to be NP-complete for general graphs, Fr\"ohlich and Ruzika show that the problem can be solved in polynomial time when $G$ is a tree, providing an $O(n^7 r)$-time algorithm. We give an efficient $O(nr^2)$-time dynamic programming algorithm for REIC on trees that is fixed-parameter linear in $n$. Evaluating our solution on a benchmark of randomly generated tree networks with baselines of the Fr\"ohlich and Ruzika algorithm and the Gurobi integer program solver, we demonstrate that in practice, our algorithm is both significantly faster and less sensitive to network topology and size. We extend our algorithm for REIC to graphs of bounded treewidth, a well-studied family of sparse graphs that generalizes trees, and obtain a matching runtime of $O(nr^2)$. We also consider the $r$-facility interdiction covering problem (RFIC), a novel variant of this network interdiction problem where the goal is to remove up to $r$ facilities to maximize the covering objective function over disconnected customers. We show that RFIC is NP-complete by observing it generalizes the small set bipartite vertex expansion problem (SSBVE), also known as the minimum $p$-union problem. We give an $O(nr^2)$-time algorithm for RFIC on trees, which also gives an $O(n^3)$-time algorithm for SSBVE on trees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper presents an O(nr^2)-time dynamic programming algorithm for the r-edge interdiction covering problem (REIC) on trees, improving the prior O(n^7 r) bound by Fröhlich and Ruzika, and shows it is fixed-parameter linear in n. The approach extends to bounded-treewidth graphs with the same runtime. For the r-facility interdiction covering problem (RFIC), the paper proves NP-completeness via generalization of the small set bipartite vertex expansion problem (SSBVE) and gives an O(nr^2)-time algorithm on trees (implying O(n^3) for SSBVE on trees). Experiments on random tree networks compare against the prior algorithm and Gurobi.

Significance. If the runtime claims hold, the reduction from O(n^7 r) to O(nr^2) with linear dependence on n constitutes a substantial algorithmic advance for interdiction problems on trees and bounded-treewidth graphs. The FPT-linear property and the extension to bounded treewidth are strengths. The NP-completeness result for RFIC together with the SSBVE connection and the O(n^3) tree algorithm are useful. The experimental comparison adds evidence of practical utility.

minor comments (1)
  1. [Abstract] Abstract: the statement that experiments demonstrate the algorithm is 'significantly faster and less sensitive' is made without any quantitative results, benchmark sizes, or specific metrics; adding one or two key numbers would improve the summary.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's core contribution is the design of a new O(nr^2)-time dynamic programming algorithm for REIC (and RFIC) on trees, obtained by a direct recurrence construction that improves the prior O(n^7 r) bound of Fröhlich and Ruzika. No equations reduce to fitted parameters, no predictions are statistically forced by inputs, and the NP-completeness claim for RFIC is established by an explicit reduction to the known SSBVE problem rather than by self-citation. The bounded-treewidth extension follows the standard Courcelle-style DP template with the same runtime once treewidth is constant. All load-bearing steps are algorithmic constructions whose correctness is argued directly from the recurrence definitions; no self-citation chain or ansatz smuggling is required for the claimed runtime or correctness.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard dynamic-programming techniques for trees and bounded-treewidth graphs; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Dynamic programming on trees yields correct optimal solutions when the recurrence covers all subtrees and boundary conditions.
    Invoked implicitly by the claim of an O(nr²) DP algorithm for REIC on trees.

pith-pipeline@v0.9.1-grok · 5870 in / 1237 out tokens · 21334 ms · 2026-06-29T09:55:41.522823+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

50 extracted references · 35 canonical work pages

  1. [1]

    Easy problems for tree-decomposable graphs.Journal of Algorithms, 12(2):308–340, 1991.doi:10.1016/0196-6774(91)90006-K

    Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs.Journal of Algorithms, 12(2):308–340, 1991.doi:10.1016/0196-6774(91)90006-K

    work page doi:10.1016/0196-6774(91)90006-k 1991

  2. [2]

    The complexity of finding most vital arcs and nodes

    Amotz Bar-Noy, Samir Khuller, and Baruch Schieber. The complexity of finding most vital arcs and nodes. Technical report, University of Maryland at College Park, 1995

    1995

  3. [3]

    Complexity of determining the most vital elements for the 1-median and 1-center location problems

    Cristina Bazgan, Sonia Toubaline, and Daniel Vanderpooten. Complexity of determining the most vital elements for the 1-median and 1-center location problems. InProceedings of the 4th International Conference on Combinatorial Optimization and Applications - Volume Part I, COCOA’10, page 237–251, Berlin, Heidelberg, 2010. Springer-Verlag

    2010

  4. [4]

    Efficient determination of thek most vital edges for the minimum spanning tree problem.Computers & Operations Research, 39(11):2888–2898, 2012.doi:10.1016/j.cor.2012.02.023

    Cristina Bazgan, Sonia Toubaline, and Daniel Vanderpooten. Efficient determination of thek most vital edges for the minimum spanning tree problem.Computers & Operations Research, 39(11):2888–2898, 2012.doi:10.1016/j.cor.2012.02.023

    work page doi:10.1016/j.cor.2012.02.023 2012

  5. [5]

    Polynomial integrality gaps for strong SDP relaxations of densestk-subgraph

    Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou. Polynomial integrality gaps for strong SDP relaxations of densestk-subgraph. InProceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 388–405, 2012.doi:10.1137/1.9781611973099.34

    work page doi:10.1137/1.9781611973099.34 2012

  6. [6]

    A linear time algorithm for finding tree-decompositions of small treewidth

    Hans L Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. InProceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 226– 234, 1993

    1993

  7. [7]

    Bonuccelli, Francesca Martelli, and Susanna Pelagatti

    Maurizio A. Bonuccelli, Francesca Martelli, and Susanna Pelagatti. Optimal packet scheduling in tree-structured LEO satellite clusters.Mob. Networks Appl., 9(4):289–295, 2004.doi: 10.1023/B:MONE.0000031588.69327.34

    work page doi:10.1023/b:mone.0000031588.69327.34 2004

  8. [8]

    Springer, 2003.doi:10.1007/0-306-48109-X_3

    Carl Burch, Robert Carr, Sven Krumke, Madhav Marathe, Cynthia Phillips, and Eric Sund- berg.A Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition, chapter 3, pages 51–68. Springer, 2003.doi:10.1007/0-306-48109-X_3

    work page doi:10.1007/0-306-48109-x_3 2003

  9. [9]

    Burton and Rodney G

    Benjamin A. Burton and Rodney G. Downey. Courcelle’s theorem for triangulations.Journal of Combinatorial Theory, Series A, 146:264–294, 2017.doi:10.1016/j.jcta.2016.10.001

    work page doi:10.1016/j.jcta.2016.10.001 2017

  10. [10]

    Chaudhry and Halim Yanikomeroglu

    Aizaz U. Chaudhry and Halim Yanikomeroglu. Laser intersatellite links in a Starlink con- stellation: A classification and analysis.IEEE Veh. Technol. Mag., 16(2):48–56, 2021. doi:10.1109/MVT.2021.3063706

    work page doi:10.1109/mvt.2021.3063706 2021

  11. [11]

    Chestnut and Rico Zenklusen

    Stephen R. Chestnut and Rico Zenklusen. Hardness and approximation for network flow interdiction.Networks, 69(4):378–387, 2017.doi:10.1002/net.21739

    work page doi:10.1002/net.21739 2017

  12. [12]

    The densestk-subhypergraph problem.SIAM Journal on Discrete Mathematics, 32(2):1458–1477, 2018.doi:10.1137/16M1096402

    Eden Chlamt´ aˇ c, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. The densestk-subhypergraph problem.SIAM Journal on Discrete Mathematics, 32(2):1458–1477, 2018.doi:10.1137/16M1096402

    work page doi:10.1137/16m1096402 2018

  13. [13]

    Minimizing the union: Tight ap- proximations for small set bipartite vertex expansion

    Eden Chlamt´ aˇ c, Michael Dinitz, and Yury Makarychev. Minimizing the union: Tight ap- proximations for small set bipartite vertex expansion. InProceedings of the 2017 An- nual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 881–899, 2017.doi: 10.1137/1.9781611974782.56. 22

    work page doi:10.1137/1.9781611974782.56 2017

  14. [14]

    The maximal covering location problem

    Richard Church and Charles ReVelle. The maximal covering location problem. InPapers of the regional science association, volume 32, pages 101–118. Springer-Verlag Berlin/Heidelberg, 1974

    1974

  15. [15]

    Church, Maria P

    Richard L. Church, Maria P. Scaparra, and Richard S. Middleton. Identifying critical infras- tructure: The median and covering facility interdiction problems.Annals of the Association of American Geographers, 94(3):491–502, 2004.doi:10.1111/j.1467-8306.2004.00410.x

    work page doi:10.1111/j.1467-8306.2004.00410.x 2004

  16. [16]

    Corley and David Y

    Herbert W. Corley and David Y. Sha. Most vital links and nodes in weighted networks.Oper. Res. Lett., 1(4):157–160, 1982.doi:10.1016/0167-6377(82)90020-7

    work page doi:10.1016/0167-6377(82)90020-7 1982

  17. [17]

    The Monadic Second-Order Logic of Graphs

    Bruno Courcelle. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs.Information and Computation, 85(1):12–75, 1990.doi:10.1016/0890-5401(90) 90043-H

    work page doi:10.1016/0890-5401(90 1990

  18. [18]

    Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33(2):125–150, 2000

    Bruno Courcelle, Johann A Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33(2):125–150, 2000

    2000

  19. [19]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, F. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

    2015

  20. [20]

    Akyildiz, and Michael D

    Eylem Ekici, Ian F. Akyildiz, and Michael D. Bender. A multicast routing algorithm for LEO satellite IP networks.IEEE/ACM Trans. Netw., 10(2):183–192, 2002.doi:10.1109/90. 993300

    work page doi:10.1109/90 2002

  21. [21]

    Application of Kuiper Systems LLC for Authority to Launch and Operate a Non-Geostationary Satellite Orbit System in Ka-band Frequencies

    Federal Communications Commission. Application of Kuiper Systems LLC for Authority to Launch and Operate a Non-Geostationary Satellite Orbit System in Ka-band Frequencies. FCC Report, 2019. URL:https://fcc.report/IBFS/SAT-LOA-20190704-00057/1773885.pdf

    2019

  22. [22]

    SPACEX NON-GEOSTATIONARY SATELLITE SYS- TEM

    Federal Communications Commission. SPACEX NON-GEOSTATIONARY SATELLITE SYS- TEM. FCC Report, 2020. URL:https://fcc.report/IBFS/SAT-MOD-20200417-00037/ 2274316.pdf

    2020

  23. [23]

    Improved approximation al- gorithms for minimum-weight vertex separators

    Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee. Improved approximation al- gorithms for minimum-weight vertex separators. InProceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 563–572, 2005

    2005

  24. [24]

    L. R. Ford and D. R. Fulkerson. Maximal flow through a network.Canadian Journal of Mathematics, 8:399–404, 1956.doi:10.4153/CJM-1956-045-5

    work page doi:10.4153/cjm-1956-045-5 1956

  25. [25]

    Frederickson and Roberto Solis-Oba

    Greg N. Frederickson and Roberto Solis-Oba. Increasing the weight of minimum spanning trees.J. Algorithms, 33(2):244–266, 1999.doi:10.1006/JAGM.1999.1026

    work page doi:10.1006/jagm.1999.1026 1999

  26. [26]

    On the hardness of covering-interdiction problems.Theor

    Nicolas Fr¨ ohlich and Stefan Ruzika. On the hardness of covering-interdiction problems.Theor. Comput. Sci., 871:1–15, 2021.doi:10.1016/J.TCS.2021.04.007

    work page doi:10.1016/j.tcs.2021.04.007 2021

  27. [27]

    Interdicting facilities in tree networks.Top, 30(1):95–118, 2022.doi:10.1007/s11750-021-00600-6

    Nicolas Fr¨ ohlich and Stefan Ruzika. Interdicting facilities in tree networks.Top, 30(1):95–118, 2022.doi:10.1007/s11750-021-00600-6

    work page doi:10.1007/s11750-021-00600-6 2022

  28. [28]

    Delbert Ray Fulkerson and Gary C. Harding. Maximizing the minimum source-sink path sub- ject to a budget constraint.Math. Program., 13(1):116–118, 1977.doi:10.1007/BF01584329. 23

    work page doi:10.1007/bf01584329 1977

  29. [29]

    An implicit enumeration algorithm for the hub interdiction median problem with fortification.Eur

    Nader Ghaffari-Nasab and Reza Atayi. An implicit enumeration algorithm for the hub interdiction median problem with fortification.Eur. J. Oper. Res., 267(1):23–39, 2018. doi:10.1016/J.EJOR.2017.11.035

    work page doi:10.1016/j.ejor.2017.11.035 2018

  30. [30]

    Reference Manual, 2025

    Gurobi. Reference Manual, 2025. URL:https://www.gurobi.com

    2025

  31. [31]

    Exploring network structure, dynamics, and function using networkx

    Aric Hagberg, Pieter J Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008

    2008

  32. [32]

    S. L. Hakimi. Optimum locations of switching centers and the absolute centers and medians of a graph.Operations Research, 12(3):450–459, 1964.doi:10.1287/opre.12.3.450

    work page doi:10.1287/opre.12.3.450 1964

  33. [33]

    Traffic engineer- ing for software-defined LEO constellations.IEEE Trans

    Menglan Hu, Mai Xiao, Wenbo Xu, Tianping Deng, Yan Dong, and Kai Peng. Traffic engineer- ing for software-defined LEO constellations.IEEE Trans. Netw. Serv. Manag., 19(4):5090– 5103, 2022.doi:10.1109/TNSM.2022.3186716

    work page doi:10.1109/tnsm.2022.3186716 2022

  34. [34]

    Kevin Wood

    Eitan Israeli and R. Kevin Wood. Shortest-path network interdiction.Networks, 40(2):97–111, 2002.doi:10.1002/NET.10039

    work page doi:10.1002/net.10039 2002

  35. [35]

    Kellerer, U

    H. Kellerer, U. Pferschy, and D. Pisinger.Knapsack Problems. Springer, 2004

    2004

  36. [36]

    Treewidth, computations and approximations

    Ton Kloks. Treewidth, computations and approximations. InLecture Notes in Computer Science, 1994

    1994

  37. [37]

    A practical approach to Courcelle’s theorem.Electronic Notes in Theoretical Computer Science, 251:65–81, 2009

    Joachim Kneis and Alexander Langer. A practical approach to Courcelle’s theorem.Electronic Notes in Theoretical Computer Science, 251:65–81, 2009. Proceedings of the International Doc- toral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2008).doi:10.1016/j.entcs.2009.08.028

    work page doi:10.1016/j.entcs.2009.08.028 2009

  38. [38]

    Courcelle’s theorem – a game- theoretic approach.Discrete Optimization, 8:568–594, 11 2011.doi:10.1016/j.disopt

    Joachim Kneis, Alexander Langer, and Peter Rossmanith. Courcelle’s theorem – a game- theoretic approach.Discrete Optimization, 8:568–594, 11 2011.doi:10.1016/j.disopt. 2011.06.001

    work page doi:10.1016/j.disopt 2011

  39. [39]

    Finding thekmost vital edges in the minimum spanning tree problem.Parallel Comput., 23(13):1889–1907, 1997.doi:10.1016/S0167-8191(97)00098-7

    Weifa Liang and Xiaojun Shen. Finding thekmost vital edges in the minimum spanning tree problem.Parallel Comput., 23(13):1889–1907, 1997.doi:10.1016/S0167-8191(97)00098-7

    work page doi:10.1016/s0167-8191(97)00098-7 1907

  40. [40]

    Almost-polynomial ratio ETH-hardness of approximating densestk- subgraph

    Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating densestk- subgraph. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Com- puting, STOC 2017, page 954–961, New York, NY, USA, 2017. Association for Computing Machinery.doi:10.1145/3055399.3055412

    work page doi:10.1145/3055399.3055412 2017

  41. [41]

    InProceedings of the 1st ACM Workshop on LEO Networking and Communication, pages 37–42, 2023

    Joseph Mclaughlin, Jee Choi, and Ramakrishnan Durairajan.×grid: A location-oriented topology design for leo satellites. InProceedings of the 1st ACM Workshop on LEO Networking and Communication, pages 37–42, 2023

    2023

  42. [42]

    Phillips

    Cynthia A. Phillips. The network inhibition problem. InProceedings of ACM Symposium on Theory of Computing (STOC), pages 776–785. ACM, 1993.doi:10.1145/167088.167286

    work page doi:10.1145/167088.167286 1993

  43. [43]

    Multiple allo- cation hub interdiction and protection problems: Model formulations and solution approaches

    Prasanna Ramamoorthy, Sachin Jayaswal, Ankur Sinha, and Navneet Vidyarthi. Multiple allo- cation hub interdiction and protection problems: Model formulations and solution approaches. Eur. J. Oper. Res., 270(1):230–245, 2018.doi:10.1016/J.EJOR.2018.03.031. 24

    work page doi:10.1016/j.ejor.2018.03.031 2018

  44. [44]

    Graph minors

    Neil Robertson and P.D Seymour. Graph minors. II. Algorithmic aspects of tree-width.Journal of Algorithms, 7(3):309–322, 1986.doi:10.1016/0196-6774(86)90023-4

    work page doi:10.1016/0196-6774(86)90023-4 1986

  45. [45]

    Snyder, Z¨ umb¨ ul Atan, Peng Peng, Ying Rong, Amanda J

    Lawrence V. Snyder, Z¨ umb¨ ul Atan, Peng Peng, Ying Rong, Amanda J. Schmitt, and Burcu Sinsoysal. OR/MS models for supply chain disruptions: A review.IIE Transactions, 48(2):89– 109, 2016.doi:10.1080/0740817X.2015.1067735

    work page doi:10.1080/0740817x.2015.1067735 2016

  46. [46]

    Continuous whole-earth coverage by circular-orbit satellite patterns

    John G Walker. Continuous whole-earth coverage by circular-orbit satellite patterns. Technical report, 1977

    1977

  47. [47]

    Li, M., Lin, S.-C., Oguz, B., Ghoshal, A., Lin, J., Mehdad, Y ., Yih, W.-t., and Chen, X

    Yikun Wang, Hewu Li, Zeqi Lai, and Jihao Li. Starmaze: Ring-based attack in satellite internet constellations. InProceedings of IEEE/ACM IWQoS, pages 1–10. IEEE, 2024.doi: 10.1109/IWQOS61813.2024.10682867

    work page doi:10.1109/iwqos61813.2024.10682867 2024

  48. [48]

    Removing arcs from a network.Operations Research, 12(6):934–940, 1964

    Richard Wollmer. Removing arcs from a network.Operations Research, 12(6):934–940, 1964. doi:10.1287/opre.12.6.934

    work page doi:10.1287/opre.12.6.934 1964

  49. [49]

    Robustness of satellite constellation networks.Comput

    Xin Xu, Zhixiang Gao, and Aijun Liu. Robustness of satellite constellation networks.Comput. Commun., 210:130–137, 2023.doi:10.1016/J.COMCOM.2023.07.036

    work page doi:10.1016/j.comcom.2023.07.036 2023

  50. [50]

    buckets,

    Rico Zenklusen. Matching interdiction.Discret. Appl. Math., 158(15):1676–1690, 2010.doi: 10.1016/J.DAM.2010.06.006. A Constrained Multiple-Choice Knapsack Problem In this section, we describe the constrained multiple-choice knapsack problem (CMCKP) and give anO(N C 2)-time dynamic programming algorithm based on the algorithm for MCKP [35, Section 11.5]. I...

    work page doi:10.1016/j.dam.2010.06.006 2010