Pith. sign in

REVIEW 3 major objections 10 minor 42 references

Sparse Relaxed Broadcast Graphs

T0 review · 3 major / 10 minor · reviewed 2026-07-09 · glm-5.2

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

Pith's one-line read Golden ratio governs the price of near-optimal broadcast networks

desk verdict Solid paper improving the overhead bound for relaxed broadcast graphs from O(n^{1-ε}) to O(n^{1-ε/α}), plus a first linear lower bound for τ=1. read the letter →

arxiv 2607.07260 v1 pith:3HWXLBPC submitted 2026-07-08 cs.DM

Pierre Fraigniaud , Hovhannes Harutyunyan This is my paper · ORCID
classification cs.DM MSC 05C35
keywords broadcastingminimumbroadcastgraphbinomialtreegoldenratiosparsitynetworkdesigninformationdissemination
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 studies how many extra communication links one must add to a tree on n nodes so that information can spread from any source to all nodes in nearly the minimum possible number of rounds. The information-theoretic floor for broadcasting to n nodes is ceil(log_2 n) rounds, since each informed node can inform at most one neighbor per round. The golden ratio phi = (1+sqrt(5))/2 enters through the constant alpha = 1/log_2(phi) - 1, which is approximately 0.44. This constant marks a natural threshold: when the allowed broadcast time exceeds (1+alpha)*log_2 n, a bare tree suffices with zero extra edges; below that threshold, extra edges are needed. The paper's central result is that for any relaxation epsilon between 0 and alpha, the overhead — the number of edges beyond the n-1 that a tree already provides — is O(n^{1-epsilon/alpha}). This improves the previous best bound of O(n^{1-epsilon}) and interpolates smoothly between the two extremes: linear overhead when epsilon approaches zero (matching a new lower bound of n/8 for powers of two), and zero overhead when epsilon reaches alpha. The construction attaches truncated binomial trees to a sparse core graph, and the edge count is optimized by a classical identity: the maximum partial sum of binomial coefficients is governed asymptotically by phi raised to the relevant power.

What carries the argument

The construction builds a graph from a core graph C (a 1-relaxed broadcast graph with at most 2*|V(C)| edges and broadcast time ceil(log_2 |V(C)|) + 1) with a truncated binomial tree B_k attached at each core node, keeping only levels 0 through m. The broadcast time of the resulting graph is at most m + d + k where d = b(C). The edge count is minimized by choosing m to maximize the partial binomial sum sum_{i=0}^{m} C(k, i), whose maximum over m is asymptotically phi^{k} (Lemma 2.1, from prior work on binomial tree broadcasting). The parameter d is set to approximately (1 - epsilon/alpha) * log_2 n, which yields the exponent 1 - epsilon/alpha in the overhead. For the lower bound, the proof (

What would settle it

An explicit construction of n-node graphs with broadcast time (1+epsilon)*log_2(n) and n + o(n^{1-epsilon/alpha}) edges for some fixed epsilon in (0, alpha) would falsify the claim that the exponent 1-epsilon/alpha is tight. Conversely, a lower bound exceeding n^{1-epsilon/alpha} for some epsilon would show the upper bound is not tight and the true overhead is larger.

Watch

Extended reading notes

Core claim

The overhead function h(n, tau) — the number of edges beyond a spanning tree needed to achieve broadcast time ceil(log_2 n) + tau — satisfies h(n, epsilon*log_2 n) = O(n^{1-epsilon/alpha}) for 0 < epsilon < alpha, where alpha = 1/log_2(phi) - 1 and phi is the golden ratio. This bound is asymptotically tight at both endpoints of the interval: it gives O(n) as epsilon approaches 0 (confirmed by a linear lower bound for 1-relaxed graphs on powers of two) and O(1) when epsilon = alpha (where trees alone suffice). The exponent 1 - epsilon/alpha arises from optimizing a tradeoff between the size of a core graph and the depth of truncated binomial trees attached to it, where the golden ratio govern

Load-bearing premise

The edge-count optimization rests on an asymptotic identity (Lemma 2.1) stating that the maximum partial sum of binomial coefficients C(s-m, i) over m is (1 +/- o(1)) * phi^s, achieved at m approximately 0.28*s. The proof absorbs the o(1) terms into big-O notation, but if the convergence to this asymptotic is slow for the parameter ranges actually used — where the relevant quantity t-d grows as roughly 2*epsilon*log_2(n) — the hidden constants in the O(n^{1-epsilon/alpha}))

Editorial extensions

If this is right

  • The minimum broadcast cost cost(n) = min over n-node graphs G of b(G)*|E(G)| satisfies cost(n) = n*log_2(n) + alpha*n*log_2(log_2(n)) + O(n), matching the known upper bound and approaching the lower bound of n*log_2(n) + Omega(n).
  • The linear lower bound of n/8 for 1-relaxed broadcast graphs on powers of two confirms that even a single round of relaxation from optimal does not eliminate the need for a linear number of extra edges, settling the order of magnitude for the smallest nontrivial relaxation.
  • The upper bound O(n^{1-epsilon/alpha}) provides a smooth interpolation between the linear-overhead regime (small epsilon) and the zero-overhead tree regime (epsilon = alpha), resolving the apparent discontinuity in the prior bound O(n^{1-epsilon}) which failed to reach zero at the threshold.

Reading between the lines

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

  • If Conjecture 2 in the paper holds — that every n-node graph with broadcast time ceil(log_2 n) + c for constant c requires n + Omega(n) edges — then the broadcast cost lower bound n*log_2(n) + Omega(n) would be tight, since one could not do better than linear overhead for any constant relaxation. This would close the gap between the cost upper and lower bounds.
  • The golden-ratio threshold alpha likely reflects a deeper structural constraint: binomial trees achieve the optimal broadcast-time-to-size ratio for trees, and the partial-sum identity governing their truncation is inherently tied to the Fibonacci recurrence. Networks that beat this ratio must add edges, and the rate at which the required edges decay is governed by the same constant.
  • The construction's reliance on a core graph with 1-relaxed broadcast time suggests a recursive or hierarchical composition strategy: one could potentially iterate the construction, using relaxed broadcast graphs as cores within larger constructions, though the paper does not explore this.
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

3 major / 10 minor

Summary. This paper studies the minimum number of edges required for n-node graphs achieving near-optimal broadcast time in the telephone model. The main result (Theorem 1.2) shows that for every epsilon in (0, alpha) where alpha = 1/log_2(phi) - 1 ~ 0.44, there exist n-node graphs with broadcast time (1+epsilon)log_2 n and n + O(n^{1-epsilon/alpha}) edges, improving the prior O(n^{1-epsilon}) overhead bound of Averbuch, Peeri, and Roditty (2017). The construction attaches truncated binomial trees to a sparse core graph. The paper also establishes a linear lower bound (Theorem 1.4): for n = 2^k, any n-node graph with broadcast time k+1 requires at least (9/8)n - O(1) edges, showing the O(n) overhead at epsilon -> 0 is tight. Finally, Theorem 1.5 slightly improves the upper bound on 1-relaxed minimum broadcast graphs to 2n - 4*ceil(log_2 n) + O(1) edges.

Significance. The paper makes a solid contribution to the network design problem for broadcasting. The upper bound O(n^{1-epsilon/alpha}) smoothly interpolates between the known O(n) overhead for 1-relaxation and the zero overhead at epsilon = alpha, resolving the question of whether a gap exists at the alpha*log_2 n threshold. The lower bound is valuable as lower bounds in this area are notoriously difficult. The proofs are combinatorial and checkable, and the construction is explicit. The result on broadcast cost (Corollary 2.2) is a nice consequence.

major comments (3)
  1. Section 2, proof of Theorem 1.2: The proof relies on Lemma 2.1, which gives the asymptotic F(s) = (1 +/- o(1)) * phi^s. The parameter t - d grows as approximately 2*epsilon*log_2(n), which tends to infinity, so the o(1) terms are legitimately absorbed into the big-O notation. This is standard asymptotic analysis and the central claim is sound. However, the proof would benefit from a brief remark acknowledging that the hidden constants in the O(n^{1-epsilon/alpha}) bound depend on the convergence rate of the o(1) terms in Lemma 2.1, and that the result is asymptotic in nature (requiring n >= n_epsilon). This is a presentation issue rather than a correctness concern.
  2. Section 2, 'Fixing the number of nodes' paragraph: The pruning step (removing nodes from truncated binomial trees to hit exactly n nodes) is argued to preserve the broadcast time bound. The argument that removing leaves cannot increase broadcast time from the root (by Fact 1.3) is correct. However, the broadcast protocol from an arbitrary source node s requires: (1) reaching the core in <= m rounds, (2) broadcasting in the core in d rounds, (3) broadcasting from each core node into its attached tree in <= k rounds. The paper should explicitly verify that pruning leaves does not increase the distance from any node to the core beyond m, which is the first step of the broadcast protocol. Since pruning only removes nodes, the distance from any remaining node to the core cannot increase, so this holds, but making this explicit would strengthen the argument.
  3. Section 3, proof of Theorem 1.4, case delta(G) = 1: The degree-distribution argument is careful but dense. The transition from counting additional edges incident to internal vertices of T_v to the minimization of A = (1/2) * sum_{i=2}^{k-2} x_i * (k-1-i) under the constraint sum x_i >= 2^{k-2} - 3 is correct. The final bound A >= 2^{k-4}(k-2) - (3/2)(k-3) leading to |E(G)| >= n - 1 + n/8 for k >= 6 is verified. The constraint sum x_i >= 2^{k-2} - 3 (rather than 2^{k-2}) accounts for the four vertices in S_k and S_{k-1} already having degree >= k-1; this should be stated more explicitly for clarity.
minor comments (10)
  1. Abstract: 'previsouly' should be 'previously'.
  2. Section 1.1, first paragraph: 'standardtelephone model' should be 'standard telephone model'.
  3. Section 1.2.1: 'Theorem 1.2 has an important corollary' -- Corollary 2.2 is stated in Section 2, not immediately after Theorem 1.2. Consider adding a forward reference.
  4. Figure 2: The caption mentions 'The dotted line is the new upper bound' but the figure description could clarify that the dotted curve represents n^{1-epsilon/alpha} and the solid curve represents n^{1-epsilon}.
  5. Section 2, proof of Theorem 1.2: The notation '(1 +/- o(1))' appears in several places (e.g., in the application of Lemma 2.1 and in Equation 1). It would be cleaner to use '(1+o(1))' consistently, noting that the o(1) term may be positive or negative but is absorbed into the asymptotic bound.
  6. Section 4, proof of Theorem 1.5: The condition k >= 8 is mentioned for the pruning to preserve that x has at least one child y in T, but the final edge count formula |E(G)| = 2(n-1) - 2(1 + (k-1) + (k-2)) = 2n - 4k + 2 is stated for k >= 6. The relationship between these thresholds should be clarified.
  7. Section 5, Equation (3): The lower bound is stated as n/8 <= h(n,1), but Theorem 1.4 gives (9/8)n - O(1) edges total, which translates to h(n,1) >= n/8 - O(1). The -O(1) term is missing in Equation (3).
  8. Table 1: The lower bound entry '1/8 n' for relaxation tau=1 should perhaps be 'n/8 - O(1)' to match the precise statement of Theorem 1.4.
  9. Section 1.2.2: 'wether B(n+1) >= B(n)' should be 'whether B(n+1) >= B(n)'.
  10. Section 2: The variable n_epsilon is introduced but the threshold for n is not explicitly quantified. A brief remark on how n_epsilon depends on epsilon would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found

full rationale

The paper is a pure combinatorial construction with self-contained proofs. The main result (Theorem 1.2) constructs a graph from a core graph C and truncated binomial trees, with parameters d, k, m derived from the broadcast time constraint and the golden ratio identity. Lemma 2.1 (cited from [23, 32, 34]) is a standalone mathematical fact about maximizing a sum of binomial coefficients, not a fitted parameter or a restatement of the target result. The lower bound (Theorem 1.4) is proved from first principles via leaf-counting in subtrees of binomial trees. Theorem 1.5 refines a prior construction by cross-wiring edges in B_k. No step in any derivation chain reduces to its own inputs by definition, and no self-citation is load-bearing in a circular way. The o(1) terms from Lemma 2.1 are legitimately absorbed into big-O notation since t-d grows to infinity with n. The pruning argument (removing leaves from truncated binomial trees to hit exactly n nodes) is justified by Fact 1.3, which states that any subtree of B_k rooted at r has broadcast time at most k from r — this is a structural property of binomial trees, not a circular assumption. The derivation is self-contained against external mathematical benchmarks.

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

No free parameters, no invented entities. The construction is parameterized by ε and n (both inputs), with d, k, m determined by optimization. The golden ratio φ and α=1/log₂φ−1 are mathematical constants, not fitted parameters.

assumptions (3)
  • standard math Lemma 2.1: max_{0≤m≤s} Σ_{i=0}^{m} C(s−m, i) = (1±o(1))φ^s, achieved at m=(1±o(1))βs where β=(√5−1)/(2√5)
    Cited from [23, 32, 34]. This is a combinatorial identity about partial sums of binomial coefficients. It is the load-bearing lemma for the upper bound; the entire edge count optimization in §2 depends on it.
  • standard math Fact 1.3: The k-dimensional binomial tree B_k has 2^k nodes, broadcast time k from the root, and any rooted tree with root-broadcast time ≤k is a subtree of B_k
    Standard property of binomial trees, used throughout the construction and lower bound.
  • domain assumption Existence of 1-relaxed broadcast graphs with ≤2ν edges and broadcast time ⌈log₂ ν⌉+1 (Theorem 1.5 / [19])
    Used to construct the core graph C in the proof of Theorem 1.2. The paper proves a slightly improved version (Theorem 1.5) but relies on the existence of such graphs as a building block.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparse Relaxed Broadcast Graphs." pith.science (2026). https://pith.science/paper/3HWXLBPC

@misc{pith2026260707260,
  author       = {Pith},
  title        = {Pith review of: Sparse Relaxed Broadcast Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3HWXLBPC}},
  note         = {Machine review of arXiv:2607.07260}
}
abstract

Broadcasting in graphs refers to the information dissemination problem in which a source node has an atomic piece of information to be distributed to all the nodes of a graph. In the standard telephone model, broadcasting proceeds as a sequence of synchronous rounds, where, at each round, every informed node can transfer the information to at most one of its neighbors. The broadcast time of a graph $G$ is the maximum, taken over every node $v\in V(G)$, of the minimum number of rounds required for broadcasting from $v$ in $G$. We study the network design problem that, for every $\epsilon> 0$, asks for the minimum number of edges of $n$-node graphs with broadcast time close to optimal, i.e., at most $(1+\epsilon)\log_2n$. Let $\phi=(1+\sqrt{5})/2$ be the golden ratio, and let $\alpha=1/\log_2\phi-1\simeq 0.44$. We show that, for every $n\geq 1$, and for every $\epsilon\in(0,\alpha)$, it suffices to add $O(n^{1-\epsilon/\alpha})$ edges to a well chosen $n$-node tree for designing an $n$-node graph with broadcast time $(1+\epsilon)\log_2n$. This asymptotic bound on the additional number of edges improves the previsouly known bound $O(n^{1-\epsilon})$, and has implications to the design of graphs with minimum broadcast cost, defined as number of edges times broadcast time. Moreover, we show that, for infinitely many values of $n$, $\Omega(n)$ edges must be added to some tree for designing an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$. Therefore, our bound $O(n^{1-\epsilon/\alpha})$ on the additional number of edges for $0<\epsilon<\alpha$ is asymptotically tight at the two extremities of the interval $(0,\alpha]$, as it is $O(n)$ when $\epsilon\to 0$, and $O(1)$ when $\epsilon=\alpha$. Finally, we show that, for every $n$, there exists an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$ and at most $2n-4\lceil\log_2n\rceil+O(1)$ edges.

Figures

Figures reproduced from arXiv: 2607.07260 by the authors.

Figure 1
Figure 1. A 12-node graph G, with broadcast time b(G) = 4 = ⌈log2 12⌉, taken from [14]. A broadcast protocol from node s, as well as the one from node s ′ , is illustrated in bold, where the numbers indicate the rounds at which the calls take place. This graph has 15 edges, and no 12-node graphs with less than 15 edges can achieve broadcast time at most 4 (see [14]), hence the minimum number of edges of 12-node graphs guarant… view at source ↗
Figure 2
Figure 2. Best known upper bounds on the overhead h(n, τ ) as a function of the relaxation τ = ϵ log2 n, when the number of nodes n is fixed (and large). The plain bold points and lines represent the state of the art before this paper. The dotted line is the new upper bound on the overhead provided in this paper. The parameter α ≃ 0.44 is defined as α = 1/ log2 ϕ−1 where ϕ = (√ 5+1)/2 is the golden ratio. 1.2 Our Results Our … view at source ↗
Figure 3
Figure 3. Illustration of our construction. (a) Our graph G consists of a core graph C to which is attached a tree Tv at each node v. Each tree Tv is isomorphic to a “truncated” Binomial tree Bk at level m. (b) A k-dimensional Binomial tree Bk for k = 4. The doted box displays B4 truncated at level m = 2 (the root is at level 0). and, last but not least, the number of edges |E(G)| of G is minimized, where |E(G)| = |E(C)| + |V… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The Binomial tree B4 contains a 8-node subtree with two leaves, and the Binomial tree B5 contains a 16-node subtree with four leaves. In general, for k ≥ 2, the Binomial tree Bk contains a 2 k−1 -node subtree with 2 k−3 leaves, which is the least number of leaves for a…
Figure 5
Figure 5. Figure 5: Illustration of the construction in the proof of Theorem 1.5. The Binomial tree Bk is composed of two Binomial trees Bk−1, each one composed of two trees Bk−2. The sets R, S, R′ , S′ are the respective children of the four roots r, s, r′ , s′ of these four trees. to co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    Ahlswede, L

    R. Ahlswede, L. Gargano, H. S. Haroutunian, and L. H. Khachatrian. Fault-tolerant minimum broadcast networks.Networks, 27:293–307, 1996

    work page 1996

  2. [2]

    On the com- plexity of telephone broadcasting from cacti to bounded pathwidth graphs

    Aida Aminian, Shahin Kamali, Seyed Mohammad Seyed Javadi, and Sumedha. On the com- plexity of telephone broadcasting from cacti to bounded pathwidth graphs. In52nd Inter- national Colloquium on Automata, Languages, and Programming (ICALP), volume 334 of LIPIcs, pages 10:1–10:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025

    work page 2025

  3. [3]

    New upper bound onm-time-relaxedk- broadcast graphs.Networks, 70(2):72–78, 2017

    Amir Averbuch, Irete Peeri, and Yehuda Roditty. New upper bound onm-time-relaxedk- broadcast graphs.Networks, 70(2):72–78, 2017

    work page 2017

  4. [4]

    Hollander Shabtai, and Yehuda Roditty

    Avi Averbuch, R. Hollander Shabtai, and Yehuda Roditty. Efficient construction of broadcast graphs.Discret. Appl. Math., 171:9–14, 2014

    work page 2014

  5. [5]

    Breaking the lognbarrier on rumor spreading.Distributed Comput., 31(6):503–513, 2018

    Chen Avin and Robert Els¨ asser. Breaking the lognbarrier on rumor spreading.Distributed Comput., 31(6):503–513, 2018

    work page 2018

  6. [6]

    Multicasting in hetero- geneous networks

    Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Multicasting in hetero- geneous networks. In30th ACM Symposium on the Theory of Computing (STOC), pages 448–453, 1998

    work page 1998

  7. [7]

    Multiple message broadcasting in the postal model

    Amotz Bar-Noy and Shlomo Kipnis. Multiple message broadcasting in the postal model. Networks, 29(1):1–10, 1997

    work page 1997

  8. [8]

    Efficient informa- tion exchange in the random phone-call model

    Petra Berenbrink, Jurek Czyzowicz, Robert Els¨ asser, and Leszek Gasieniec. Efficient informa- tion exchange in the random phone-call model. In37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6199 ofLNCS, pages 127–138. Springer, 2010

    work page 2010

Show all 42 references
  1. [9]

    Jean-Claude Bermond, Pierre Fraigniaud, and Joseph G. Peters. Antepenultimate broadcast- ing.Networks, 26(3):125–137, 1995

    1995

  2. [10]

    Faster parameterized broadcasting

    Edouard Bonnet, Carl Feghali, and Manolis Vasilakis. Faster parameterized broadcasting. Tech. Report arXiv:2607.01770, 2026

    2026 arXiv

  3. [11]

    Dinneen, Jos´ e A

    Michael J. Dinneen, Jos´ e A. Ventura, Mark C. Wilson, and Golbon Zakeri. Construction of time relaxed minimal broadcast networks.Parallel Process. Lett., 9(1):53–68, 1999

    1999

  4. [12]

    Broadcasting un- der structural restrictions

    Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mit- sou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Broadcasting un- der structural restrictions. In50th International Symposium on Mathematical Foundations of Computer Sci...

    2025

  5. [13]

    Sublogarithmic approximation for telephone multicast: path out of jungle

    Michael Elkin and Guy Kortsarz. Sublogarithmic approximation for telephone multicast: path out of jungle. In14th ACM-SIAM Symposium on Discrete Algorithms, pages 76–85, 2003

    2003

  6. [14]

    Farley, Stephen T

    Arthur M. Farley, Stephen T. Hedetniemi, Sandra Mitchell Mitchell, and Andrzej Proskurowski. Minimum broadcast graphs.Discret. Math., 25(2):189–193, 1979. 19

    1979

  7. [15]

    Randomized broadcast in networks.Random Struct

    Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. Randomized broadcast in networks.Random Struct. Algorithms, 1(4):447–460, 1990

    1990

  8. [16]

    Fomin, Pierre Fraigniaud, and Petr A

    Fedor V. Fomin, Pierre Fraigniaud, and Petr A. Golovach. Parameterized complexity of broad- casting in graphs. In49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 14093 ofLNCS, pages 334–347. Springer, 2023

    2023

  9. [17]

    Methods and problems of communication in usual networks.Discret

    Pierre Fraigniaud and Emmanuel Lazard. Methods and problems of communication in usual networks.Discret. Appl. Math., 53(1-3):79–133, 1994

    1994

  10. [18]

    Frieze and Michael Molloy

    Alan M. Frieze and Michael Molloy. Broadcasting in random graphs.Discret. Appl. Math., 54(1):77–79, 1994

    1994

  11. [19]

    Tight bounds on minimum broadcast networks.SIAM J

    Michelangelo Grigni and David Peleg. Tight bounds on minimum broadcast networks.SIAM J. Discret. Math., 4(2):207–222, 1991

    1991

  12. [20]

    Harutyunyan

    Hovhannes A. Harutyunyan. Broadcast networks with near optimal cost. In10th International Conference on Algorithmic Aspects in Information and Management (AAIM), volume 8546 of LNCS, pages 312–322. Springer, 2014

    2014

  13. [21]

    Harutyunyan and Zhiyuan Li

    Hovhannes A. Harutyunyan and Zhiyuan Li. A simple construction of broadcast graphs. In 25th International Conference on Computing and Combinatorics (COCOON), volume 11653 ofLNCS, pages 240–253. Springer, 2019

    2019

  14. [22]

    Harutyunyan and Zhiyuan Li

    Hovhannes A. Harutyunyan and Zhiyuan Li. A new construction of broadcast graphs.Discret. Appl. Math., 280:144–155, 2020

    2020

  15. [23]

    Harutyunyan and Arthur L

    Hovhannes A. Harutyunyan and Arthur L. Liestman. k-broadcasting in trees.Networks, 38(3):163–168, 2001

    2001

  16. [24]

    Harutyunyan and Arthur L

    Hovhannes A. Harutyunyan and Arthur L. Liestman. On the monotonicity of the broadcast function.Discret. Math., 262(1-3):149–157, 2003

    2003

  17. [25]

    Harutyunyan and Arthur L

    Hovhannes A. Harutyunyan and Arthur L. Liestman. Upper bounds on the broadcast function using minimum dominating sets.Discret. Math., 312(20):2992–2996, 2012

    2012

  18. [26]

    Harutyunyan, Arthur L

    Hovhannes A. Harutyunyan, Arthur L. Liestman, Joseph G. Peters, and Dana Richards.The Handbook of Graph Theory, chapter Broadcasting and Gossiping, pages 1477–1494. Chapman and Hall, 2013

    2013

  19. [27]

    Hedetniemi, and Arthur L

    Sandra Mitchell Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liestman. A survey of gossiping and broadcasting in communication networks.Networks, 18(4):319–349, 1988

    1988

  20. [28]

    Texts in Theoretical Computer Science

    Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger.Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2005

    2005

  21. [29]

    Lennart Johnsson and Ching-Tien Ho

    S. Lennart Johnsson and Ching-Tien Ho. Optimum broadcasting and personalized communi- cation in hypercubes.IEEE Trans. Computers, 38(9):1249–1268, 1989. 20

    1989

  22. [30]

    Karp, Christian Schindelhauer, Scott Shenker, and Berthold V¨ ocking

    Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold V¨ ocking. Randomized rumor spreading. In41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 565–574, 2000

    2000

  23. [31]

    L. H. Khachatrian and O. S. Harutounian. Construction of new classes of minimal broadcast networks. Conference on Coding Theory in Armenia, 1990

    1990

  24. [32]

    Minimal broadcast trees

    Levon Khachatrian and Hovhannes Haroutunian. Minimal broadcast trees. InXIV Moscow–Minsk All Union School of Computing Networks, page 36–40, 1989

    1989

  25. [33]

    Approximation algorithms for minimum-time broadcast.SIAM J

    Guy Kortsarz and David Peleg. Approximation algorithms for minimum-time broadcast.SIAM J. Discret. Math., 8(3):401–427, 1995

    1995

  26. [34]

    Extremal broadcasting problems.Discret

    Roger Labahn. Extremal broadcasting problems.Discret. Appl. Math., 23(2):139–155, 1989

    1989

  27. [35]

    Liestman

    Arthur L. Liestman. Fault-tolerant broadcast graphs.Networks, 15(2):159–171, 1985

    1985

  28. [36]

    R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In35th IEEE Symposium on Foundations of Computer Science (FOCS), pages 202–213, 1994

    1994

  29. [37]

    Rieksts and Jos´ e A

    Brian Q. Rieksts and Jos´ e A. Ventura. Time-relaxed 1-fault tolerant broadcast networks. Parallel Process. Lett., 19(2):335–353, 2009

    2009

  30. [38]

    Time-relaxed broadcasting in communication networks.Discret

    Aditya Shastri. Time-relaxed broadcasting in communication networks.Discret. Appl. Math., 83(1-3):263–278, 1998

    1998

  31. [39]

    Slater, Ernest J

    Peter J. Slater, Ernest J. Cockayne, and Stephen T. Hedetniemi. Information dissemination in trees.SIAM J. Comput., 10(4):692–701, 1981

    1981

  32. [40]

    Telephone broadcast on graphs of treewidth two.Theor

    Prafullkumar Tale. Telephone broadcast on graphs of treewidth two.Theor. Comput. Sci., 1045:115282, 2025

    2025

  33. [41]

    Ventura and Xiaohua Weng

    Jos´ e A. Ventura and Xiaohua Weng. A new method for constructing minimal broadcast networks.Networks, 23(5):481–497, 1993

    1993

  34. [42]

    Weng and Jos´ e A

    Michael X. Weng and Jos´ e A. Ventura. A doubling procedure for constructing minimal broad- cast networks.Telecommun. Syst., 3(3):259–293, 1994. 21

    1994

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.