Pith. sign in

REVIEW 2 major objections 5 minor 39 references

Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A minmax-regret broadcast center on a tree with interval edge weights can be found in O(n log n log log n) time.

desk verdict First minmax-regret broadcast center algorithm for trees with interval weights; the flagged α inconsistency is a typo and the core proofs hold up under close reading. read the letter →

arxiv 2411.17271 v1 pith:34CVWBSM submitted 2024-11-26 cs.DS

Cheng-Hsiao Tsou , Ching-Chi Lin , Gen-Huey Chen This is my paper · ORCID
classification cs.DS MSC 68R1005C8568W40
keywords broadcastingminmax-regrettreenetworkedgeweightuncertaintypostalmodelworst-casescenarioprune-and-searchintervalweights
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

This paper claims that the robust broadcasting problem on a tree—where each edge weight is only known to lie in an interval and the goal is to choose one broadcast center that minimizes the worst-case regret—can be solved in $O(n\log n\log\log n)$ time under the postal model. That matters because choosing a message source without knowing actual bandwidths can otherwise be badly suboptimal, and a naive search over all edge-weight scenarios is infinite. The paper shows that for each candidate vertex the infinite scenario space can be collapsed to at most $n-1$ candidate scenarios, and that a centroid-based prune-and-search needs only $O(\log n)$ rounds. A sympathetic reader would take the contribution as showing that minmax-regret broadcasting on trees with interval weights and a positive per-call setup cost $\rho$ is solvable in near-linear time rather than requiring exhaustive scenario search.

What carries the argument

The load-bearing machinery is the base scenario $\alpha_{x,y}$ and its derived scenarios $\beta^j_{x,y}$, indexed by the neighbors $u_{i,1},\ldots,u_{i,h_i}$ of a candidate vertex $v_i$ outside the branch containing $x$. Facts 1 and 2 assert that a worst-case scenario can be assumed to agree with $\alpha_{x,y}$ on the $x$-to-$y$ path and on the component $B_{y,x}$, while Facts 3 and 4 fix the remaining branch weights, so the true worst case lies among at most $n-1$ candidates. The broadcast-time decomposition of Lemma 4, $b\text{times}(x,T)=d_{x,\kappa}\rho+\tilde{w}^s_{x,\kappa}+b\text{times}(\kappa,\bar{B}_{\kappa,x})$, turns regret comparisons into path-weight sums plus two subtree broadcast times, and Lemma 13 says the best candidate maximizes exactly that combination. Bucket structures storing $\text{acc}(\ell)$ and $\min v(\ell)$, together with a van Emde Boas priority queue, maintain the optimal broadcast sequence across all $\beta^j_{x,y}$ in $O(n\log\log n)$ time per source.

What would settle it

Take a small tree with interval weights and positive $\rho$, run Algorithm 2 to obtain every candidate scenario $\beta^j_{x,y}$, then sample a dense grid of actual scenarios from the interval product $C$ and compute the relative regret $r^s_{x,y}$ for each sample; if any sampled scenario gives a strictly larger regret than every candidate $\beta$, the scenario reduction is false and the algorithm's output cannot be certified as a worst-case scenario.

Watch

Extended reading notes

Core claim

The central claim is that a minmax-regret broadcast center of an $n$-vertex tree with interval edge weights, under the postal model with connection time $\rho>0$, can be computed in $O(n\log n\log\log n)$ time. For any fixed candidate source $x$, the paper constructs a finite family of scenarios with at most $n-1$ members total, and proves, through a chain of scenario transformations, that some member of this family is a worst-case scenario for $x$. This reduces the infinite maximum-regret computation to evaluating $O(n)$ specially defined scenarios $\beta^j_{x,v_i}$. The paper then shows that evaluating all of them, after $O(n\log n)$ preprocessing, takes $O(n\log\log n)$ time per vertex, and that the centroid-based search visits $O(\log n)$ subtrees, yielding the stated bound.

Load-bearing premise

The whole argument depends on Facts 1 and 2: that every worst-case scenario can be transformed, without reducing the regret, into one whose weights on the path from $x$ to $y$ and on the branch containing $y$ are at the extreme values of the base scenario $\alpha_{x,y}$; if that collapse misses the true worst case, the candidate set is too small and Algorithm 2 can return a scenario that is not actually worst-case.

Editorial extensions

If this is right

  • Network operators on tree topologies can choose a broadcast source whose worst-case loss is minimized, even when link delays are known only as ranges, in time nearly linear in the network size.
  • The infinite scenario space of minmax regret on trees is shown to reduce to a finite candidate set of size at most $n-1$ per source, a structural fact usable in other robust tree-location problems.
  • Setting the postal-model parameter $\rho=0$ recovers a robust 1-center problem, so the known $O(n\log n)$ robust 1-center result becomes the special case of a single algorithm with an extra $O(\log\log n)$ factor.
  • The result marks the tree case of robust broadcasting with interval weights as polynomial, leaving NP-hardness only for general topologies.

Reading between the lines

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

  • The $O(\log\log n)$ factor enters through the van Emde Boas priority queue rather than through the combinatorial structure, so in special cases such as $\rho=0$ a different bucketing scheme might remove that factor entirely.
  • The scenario-collapse recipe—find a finite extreme-point scenario family for the structural optimum, then prune-and-search over centroids—likely transfers to other communication models on trees, such as the telephone or cable model, where a broadcast center is defined by different recurrence relations.
  • A direct empirical validation would enumerate all vertices on small random trees, sample the interval scenario space densely, and confirm that the $\beta$ candidates always attain at least the sampled regrets; a violation would pinpoint exactly which of Facts 1–4 fails.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper considers the broadcast-center problem on a tree under the postal model when every edge weight is an interval of possible values, and adopts the minmax-regret criterion. The central claim is Theorem 9: a minmax-regret broadcast center of an n-vertex tree with interval edge weights can be computed in O(n log n log log n) time. The proposed method is a prune-and-search procedure (Algorithm 1) that repeatedly chooses a centroid x of the current search region, computes a worst-case scenario for x, and applies Lemma 7 to restrict the search. The main technical contribution is the reduction of the infinite scenario space for each vertex x to at most n-1 candidate scenarios, constructed from base scenarios α_{x,v_i} and modified scenarios β^j_{x,v_i}. Correctness is developed through Facts 1-4 and Lemmas 10-13, and the O(n log log n) worst-case-scenario search is based on bucket structures, predecessor/successor lists, and van Emde Boas priority queues.

Significance. If the claimed result is correct, it is a substantial algorithmic contribution: it extends deterministic postal-model broadcasting [33] to robust optimization under interval edge weights, and it does so with the same type of bound as the robust 1-center problem of Burkard and Dollani up to an O(log log n) factor. The paper contains a fully specified algorithm, a parameter-free finite scenario reduction, and a serious attempt at a self-contained correctness proof. The use of a finite candidate set for the worst-case scenario is the key idea and is falsifiable in the sense that the proof gives explicit scenarios that are claimed to attain the maximum regret. The main proof is not machine-checked, and the complexity analysis depends on a long and intricate successor-list construction, so the significance should be read as conditional on the completeness of that analysis.

major comments (2)
  1. [Section 5, paragraph after Lemma 13] The proof of the O(n log log n) evaluation of the maximum in Lemma 13 is incomplete. The text states that b_time^{β^j}_{x,v_i}(v_i, \bar B_{v_i,x}) "and b_time^{β^j}_{x,v_i}(v_i,T) similarly" can be determined in O(n log log n) time, but then the detailed bucket/pred/succ construction is given only for b_time^{β^j}_{x,v_i}(v_i, \bar B_{v_i,x}). The two quantities are not literally the same: broadcasting from v_i to all of T includes the additional neighbor µ in B_{v_i,x}, and the position of µ in the optimal neighbor ordering, as well as the positions of the u_{i,k} with smaller values, depends on β^j. Since Lemma 13's expression subtracts b_time^{β^j}(v_i,T), an incorrect or omitted evaluation would change the scenario selected. Please provide the details of how µ is folded into the bucket/pred/succ structure, or give a separate derivation of the full broadcast time, and confirm that the O(h_i log log h_i) bound is preserved.
  2. [Section 5.1, paragraph 'The overall time complexity...'] The inequality Σ_{1≤j≤h_i} δ_j ≤ 2(h_i-1) is asserted rather than proved. Here δ_j is the number of buckets deleted from succ(j+1) when constructing succ(j). The preceding sentence accounts for buckets newly added to some succ(j) (at most two per step), but it does not rule out the possibility that a bucket index is deleted at one level and reinserted at a later (smaller) level. If reinsertion can occur, Σ δ_j could be larger, and the O(h_i log log h_i) bound for the deletions would fail. Because this bound is load-bearing for the claimed overall complexity, please supply an explicit charging argument showing that each deleted bucket is charged to a distinct creation event, or prove a monotonicity property that prevents reinsertion.
minor comments (5)
  1. [Section 3, definition of α_{x,v_i}] The definition sets w^{α_{x,v_i}}_{a,b}=w^+_{a,b} on P(x,v_i) ∪ E(\bar B_{v_i,x}), while Facts 1 and 2 refer to weights on P_{x,y} ∪ E(B_{y,x}). These are consistent because B_{y,x} is the x-side component and E(B_{y,x}) is exactly the set on which α takes the lower endpoints, but the paper should state this reconciliation explicitly to avoid the apparent mismatch.
  2. [Algorithm 1, lines 4-9] The pseudocode does not explicitly say that, in every iteration, ¨s(z), BCtr^{¨s(z)}, and B_{z,κ} in line 8 are all evaluated with respect to the original input tree T, not with respect to the current subtree T′. The surrounding text indicates this, but the ambiguity is important because Lemma 7 is a statement about the original T; please add a sentence or a note to the pseudocode.
  3. [Abstract and Table 1] There are several typographical errors: 'Th e broadcasting' in the abstract and 'wights' in Table 1 should be corrected. These do not affect the mathematics.
  4. [Section 5.1, definitions of pred(j) and succ(j)] The definitions of pred(j) and succ(j) as lists of non-empty buckets are dense and would benefit from a short intuitive explanation: pred(j) records the buckets to the left of τ_j that are possible bottlenecks for the prefix, and succ(j) records the analogous buckets to the right. This would make the four stages of the construction much easier to follow.
  5. [Section 4.4, definition of t*] The existence and role of Q_{t*} is proved inline after the definition, but a high-level sentence stating that t* is the first moment when the bottleneck of the y-to-\bar B_{y,x} broadcast is the next vertex to be fixed would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the scenario-reduction facts are proved from the postal model and prior independent building blocks, not assumed into the result.

full rationale

The paper's central derivation is the reduction of the infinite scenario space to the finite candidate set \Psi_1(x) \cup ... \cup \Psi_n(x). This reduction is not circular: Facts 1-4 are proved explicitly, using Lemma 1, Lemma 2, and Lemma 8 from the earlier deterministic broadcasting paper [33] plus Lemmas 4-6 proved in the present work. Those cited lemmas are parameter-free statements about the postal model that do not assume the target minmax-regret result, and they are used as building blocks rather than as the conclusion. The apparent mismatch between the definition of \alpha_{x,y} (high on P_{x,y} \cup E(\bar{B}_{y,x})) and its use in Facts 1-2 (on P_{x,y} \cup E(B_{y,x})) is a notational subset issue: Facts 1-2 fix only a subset of coordinates to \alpha_{x,y} and leave the remaining coordinates to the running worst-case scenario, so the candidate scenarios are not the worst-case scenario by construction. Lemma 13 gives a sufficient condition for \beta^{j'}_{x,y'} = \ddot{s}(x) and is proved from Facts 3-4 and Lemma 5, not assumed. The complexity analysis is independent of any fitted value. Citations to [33] are self-citations in part, but they are mathematically substantive prior results used as lemmas, and the core claim---an O(n log n log log n)-time minmax-regret algorithm for uncertain weights---does not reduce to those lemmas or to [14]. No circular step can be exhibited.

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

The algorithm introduces no new physical entities or fitted constants. The only parameter rho is a positive constant given by the postal model, not fitted. All assumptions are either standard minmax-regret modeling or external algorithmic results from the cited literature, primarily [33] and centroid-finding results.

assumptions (4)
  • domain assumption The broadcast-time formulas and structural lemmas (Lemmas 1, 2, 4, 8) of Su, Lin, and Lee [33] for the deterministic postal model are correct.
    Invoked throughout: Lemma 1 in Section 2, Lemma 4 in the proof of Lemma 7, Lemma 8 for optimal broadcast sequences. These are external results from a prior paper by one of the present authors.
  • domain assumption The minmax-regret objective is well-defined over the Cartesian product of intervals C, and a worst-case scenario exists.
    Section 2 defines C and max r(x); the paper assumes a maximizing scenario exists without specifying a distribution. This is standard in minmax regret but is an assumption about the problem setup.
  • domain assumption The edge weight intervals [w-, w+] are predetermined, independent, and non-negative.
    Section 2 states 'C is predetermined'. The algorithm does not model correlations or distributions; it uses interval uncertainty as the only information.
  • domain assumption A centroid of a tree can be found in O(n) time and the largest open z-branch contains at most floor(n/2) vertices.
    Used in Algorithm 1 to obtain O(log n) iterations; this is a known result from [19, 23] and is not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty." pith.science (2026). https://pith.science/paper/34CVWBSM

@misc{pith2026241117271,
  author       = {Pith},
  title        = {Pith review of: Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/34CVWBSM}},
  note         = {Machine review of arXiv:2411.17271}
}
abstract

A broadcasting problem in heterogeneous tree networks with edge weight uncertainty under the postal model is considered in this paper. The broadcasting problem asks for a minmax-regret broadcast center, which minimizes the worst-case loss in the objective function. Due to the presence of edge weight uncertainty, it is not easy to attack the broadcasting problem. An $O(n \log n \log \log n)$-time algorithm is proposed for solving the broadcasting problem.

Figures

Figures reproduced from arXiv: 2411.17271 by the authors.

Figure 1
Figure 1. A tree T. Clearly, C is an infinite set. A tuple s = (s1, s2, . . . , sn−1) is called a scenario of T, if s ∈ C. For the example of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Bx,y and B¯ x,y. Lemma 1 ([33]) Suppose s ∈ C and (u, v) ∈ E(T). If b times (u, B¯ u,v) ≤ b times (v, B¯ v,u), then the following hold: • b times (u, T) = ρ + w s u,v + b times (v, B¯ v,u); • b times (v, T) ≤ b times (u, T). A tree is a star, if it has one or two vertices, or has exactly one vertex whose degree is greater than one. The latter is called the center of the star. For the one-vertex star, the vertex is t… view at source ↗
Figure 3
Figure 3. proof of Lemma 4. Also notice that dx,κˆ · ρ + ˜w s x,κˆ in Lemma 4 is the minimum time requirement for x to broadcast a message along the x-to-ˆκ path. Actually, Lemma 4 reveals that b times (x, T) can be calculated as the minimum time requirement for x to broadcast a message over a subgraph, i.e., the union of the x-to-ˆκ path and B¯ κ,x ˆ , of T. Moreover, the proof of Lemma 4 shows that an optimal transmission s… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: An illustrative example with ρ = 1. (a) A tree T. (b) The base scenario αx,vi . Lemma 8 [33] Suppose x ∈ V (T), s ∈ C, and NT (x) = {u1, u2, . . . , uh}, where h = |NT (x)|. If w s x,uk + b times (uk, B¯ uk,x) is nonincreasing as k increases from 1 to h, then u1, u2, .…
Figure 5
Figure 5. Figure 5: Two instances of β j x,vi . (a) β 1 x,vi . (b) β 2 x,vi . 11 [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Comparison between γ j x,y and β j x,y. Q0 is an optimal sequence for y to broadcast a message to NB¯y,x (y) under γ 0 x,y. More￾over, for 1 ≤ j ≤ h, let Qj = (qj,1, qj,2, . . . , qj,h) be the sequence obtained from Qj−1 = (qj−1,1, qj−1,2, . . . , qj−1,h) by cyclically…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [33]

    Su, C.-C

    Y.-H. Su, C.-C. Lin, and D. T. Lee. Broadcasting in weigh ted trees under the postal model. Theoret. Comput. Sci. , 621:73–81, 2016

    work page 2016

  2. [1]

    Albouy, D

    T. Albouy, D. Frey, M. Raynal, and F. Ta ¨ ıani. Asynchronous Byzantine reliable broadcast with a message adversary. Theoret. Comput. Sci. , 978:114110, 2023

    work page 2023

  3. [2]

    G. P. Arumugam, J. Augustine, M. J. Golin, and P. Srikanth an. Minmax regret k-sink location on a dynamic path network with uniform capacities. Algorithmica, 81(9):3534– 3585, 2019

    work page 2019

  4. [3]

    Averbakh

    I. Averbakh. On the complexity of a class of combinatoria l optimization problems with uncertainty. Mathematical Programming, 90(2, Ser. A):263–272, 2001

    work page 2001

  5. [4]

    Averbakh

    I. Averbakh. Minmax regret linear resource allocation p roblems. Operations Research Letters, 32(2):174–180, 2004

    work page 2004

  6. [5]

    Averbakh and S

    I. Averbakh and S. Bereg. Facility location problems wit h uncertainty on the plane. Discrete Optimization, 2(1):3–34, 2005

    work page 2005

  7. [6]

    Averbakh and O

    I. Averbakh and O. Berman. Minimax regret p-center location on a network with demand uncertainty. Location Science, 5(4):247–254, 1997

    work page 1997

  8. [7]

    Averbakh and O

    I. Averbakh and O. Berman. Algorithms for the robust 1-ce nter problem on a tree. European Journal of Operational Research , 123(2):292–302, 2000

    work page 2000

Show all 39 references
  1. [8]

    Averbakh and O

    I. Averbakh and O. Berman. Minmax regret median location on a network under uncer- tainty. INFORMS Journal on Computing , 12(2):104–110, 2000

    2000

  2. [9]

    Bar-Noy, S

    A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Message mul ticasting in heterogeneous networks. SIAM Journal on Computing , 30(2):347–358, 2000

    2000

  3. [10]

    Bar-Noy and S

    A. Bar-Noy and S. Kipnis. Designing broadcasting algor ithms in the postal model for message-passing systems. Mathematical Systems Theory , 27(5):431–452, 1994

    1994

  4. [11]

    Bar-Noy and S

    A. Bar-Noy and S. Kipnis. Multiple message broadcastin g in the postal model. Networks, 29(1):1–10, 1997. 38

    1997

  5. [12]

    Bhattacharya, T

    B. Bhattacharya, T. Kameda, and Z. Song. A linear time al gorithm for computing minmax regret 1-median on a tree network. Algorithmica, 70(1):2–21, 2014

    2014

  6. [13]

    Bortolussi, J

    L. Bortolussi, J. Hillston, and M. Loreti. Fluid approx imation of broadcasting systems. Theoret. Comput. Sci. , 816:221–248, 2020

    2020

  7. [14]

    R. E. Burkard and H. Dollani. A note on the robust 1-cente r problem on trees. Annals of Operations Research, 110(1–4):69–82, 2002

    2002

  8. [15]

    E. Conde. On the complexity of the continuous unbounded knapsack problem with uncer- tain coefficients. Operations Research Letters, 33(5):481–485, 2005

    2005

  9. [16]

    T. T. Dam, T. A. Ta, and T. Mai. Robust maximum capture fac ility location under random utility maximization models. European J. Oper. Res. , 310(3):1128–1150, 2023

    2023

  10. [17]

    Drwal and J

    M. Drwal and J. J´ ozefczyk. Robust min-max regret sched uling to minimize the weighted number of late jobs with interval processing times. Ann. Oper. Res. , 284(1):263–282, 2020

    2020

  11. [18]

    Dvir and G

    D. Dvir and G. Y. Handler. The absolute center of a networ k. Networks, 43(2):109–118, 2004

    2004

  12. [19]

    A. J. Goldman. Optimal center location in simple networ ks. Transportation Science, 5(2):212–221, 1971

    1971

  13. [20]

    H. A. Harutyunyan, A. L. Liestman, K. Makino, and T. C. Sh ermer. Nonadaptive broad- casting in trees. Networks, 57(2):157–168, 2011

    2011

  14. [21]

    H. A. Harutyunyan, A. L. Liestman, and B. Shao. A linear a lgorithm for finding the k-broadcast center of a tree. Networks, 53(3):287–292, 2009

    2009

  15. [22]

    Hsu, W.-C

    C.-L. Hsu, W.-C. Lin, L. Duan, J.-R. Liao, C.-C. Wu, and J .-H. Chen. A robust two- machine flow-shop scheduling model with scenario-dependen t processing times. Discrete Dyn. Nat. Soc. , 2020

    2020

  16. [23]

    A. N. C. Kang and D. A. Ault. Some properties of a centroid of a free tree. Information Processing Letters, 4(1):18–20, 1975/76

    1975

  17. [24]

    Khuller, Y.-A

    S. Khuller, Y.-A. Kim, and Y.-C. Wan. On generalized gos siping and broadcasting. Journal of Algorithms , 59(2):81–106, 2006

    2006

  18. [25]

    Kouvelis and G

    P. Kouvelis and G. Yu. Robust discrete optimization and its applications , volume 14 of Non- convex Optimization and its Applications , pages xvi+356. Kluwer Academic Publishers, Dordrecht, 1997

    1997

  19. [26]

    D. R. Kowalski, M. A. Mosteiro, and K. Zaki. Dynamic mult iple-message broadcast: bounding throughput in the affectance model. Theory Comput. Syst. , 67(4):825–854, 2023

    2023

  20. [27]

    Labb´ e, J.-F

    M. Labb´ e, J.-F. Thisse, and R. E. Wendell. Sensitivity analysis in minisum facility location problems. Operations Research, 39(6):961–969, 1991

    1991

  21. [28]

    Liao and Y

    W. Liao and Y. Fu. Min-max regret criterion-based robus t model for the permutation flow-shop scheduling problem. Eng. Optim. , 52(4):687–700, 2020

    2020

  22. [29]

    P. B. Mirchandani and A. R. Odoni. Locations of medians o n stochastic networks. Trans- portation Science, 13(2):85–97, 1979. 39

    1979

  23. [30]

    Y. Nikulin. Robustness in combinatorial optimization and scheduling theory: An extended annotated bibliography. Technical report, Christian-Alb rechts-Universitat zu Kiel, Institut fur Betriebswirtschaftslehre, 01 2004

    2004

  24. [31]

    Richards and A

    D. Richards and A. L. Liestman. Generalizations of broa dcasting and gossiping. Networks, 18(2):125–138, 1988

    1988

  25. [32]

    P. J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Infor mation dissemination in trees. SIAM J. Comput. , 10(4):692–701, 1981

    1981

  26. [34]

    van Emde Boas, R

    P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and imp lementation of an efficient priority queue. Theory of Computing Systems , 10(1):99–127, 1976

    1976

  27. [35]

    ˇCevnik and J

    M. ˇCevnik and J. ˇZerovnik. Broadcasting on cactus graphs. J. Comb. Optim. , 33(1):292– 316, 2017

    2017

  28. [36]

    B.-F. Wang. Efficient algorithms for the minmax regret pa th center problem with length constraint on trees. Theoret. Comput. Sci. , 918:18–31, 2022

    2022

  29. [37]

    Wang, J.-H

    B.-F. Wang, J.-H. Ye, and C.-Y. Li. An improved algorith m for the minmax regret path center problem on trees. J. Comput. System Sci. , 114:36–47, 2020

    2020

  30. [38]

    Ye and B.-F

    J.-H. Ye and B.-F. Wang. On the minmax regret path median problem on trees. J. Comput. System Sci. , 81(7):1159–1170, 2015

    2015

  31. [39]

    Yu, T.-C

    H.-I. Yu, T.-C. Lin, and B.-F. Wang. Improved algorithm s for the minmax-regret 1-center and 1-median problems. ACM Transactions on Algorithms , 4(3):Art. 36, 27, 2008. 40

    2008

Pith tools

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