Kamali, ShahinSeyed Javadi, Seyed Mohammad2025-11-112025-11-112025-08-082025-11-11https://hdl.handle.net/10315/43337In Telephone Broadcasting, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. We study the problem in cactus graphs and graphs of bounded pathwidth. Despite many previous efforts, the complexity of the problem in cactus graphs remained open. We settle this question by establishing the NP-completeness of broadcasting in cactus graphs and graphs of pathwdith 2. On the positive side, we present constant-factor approximation algorithms for the studied families of graphs, namely, an algorithm with an approximation factor of 2 for cactus graphs and an approximation factor of O(1) for graphs of constant pathwidth.Author owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.Computer scienceTheoretical mathematicsElectronic Thesis or Dissertation2025-11-11Telephone broadcastingApproximation algorithmsNP-hardnessCactus graphs