The Telephone k-Multicast Problem
Algorithmica · 2026-04 · 88 (2)
DOI: 10.1007/s00453-026-01377-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 02.03.2026. Verfasst von Daniel Hathcock und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation Graduate Research Fellowship Program, Air Force Office of Scientific Research.
Abstract (Originalsprache)
We consider minimum time multicasting problems in directed and undirected graphs: given a root node and a subset of t terminal nodes, multicasting seeks to find the minimum number of rounds within which all terminals can be informed with a message originating at the root. In each round, the telephone model we study allows the information to move via a matching from the informed nodes to the uninformed nodes. Since minimum time multicasting in digraphs is poorly understood compared to the undirected variant, we study an intermediate problem in undirected graphs that specifies a target $$k < t$$ k < t , and requires that only k of the terminals be informed in the minimum number of rounds. For this problem, we improve the implications of the previous results and obtain a multiplicative approximation factor of $$\tilde{O}(t^{1/3})$$ O ~ ( t 1 / 3 ) . For the directed version, we obtain an additive $$\tilde{O}(k^{1/2})$$ O ~ ( k 1 / 2 ) approximation algorithm (with a polylogarithmic multiplicative factor). Our algorithms are based on reductions to the related problems of finding k -trees of minimum poise (sum of maximum degree and diameter) and applying a combination of greedy network decomposition techniques and set covering under partition matroid constraints. We also study the problem of bounded degree Directed Steiner Tree, for which we obtain improved polylogarithmic approximations for the special case of bounded treewidth graphs. This extends prior work on the Group Steiner Tree problem.
Förderung
- National Science Foundation Graduate Research Fellowship Program
- Air Force Office of Scientific Research
Zitieren
APA
Hathcock, D., Kortsarz, G., & Ravi, R. (2026). The Telephone k-Multicast Problem. Algorithmica, 88(2). https://doi.org/10.1007/s00453-026-01377-5
Vancouver
Hathcock D, Kortsarz G, Ravi R. The Telephone k-Multicast Problem. Algorithmica. 2026;88(2). doi:10.1007/s00453-026-01377-5
BibTeX
@article{Hathcock2026,
author = {Hathcock, Daniel and Kortsarz, Guy and Ravi, R.},
title = {The Telephone k-Multicast Problem},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {2},
doi = {10.1007/s00453-026-01377-5}
}
EUVIMED