EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The Telephone k-Multicast Problem

Daniel Hathcock, Guy Kortsarz, R. Ravi

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →