On the complexity of telephone broadcasting from cacti to bounded pathwidth graphs

DOI10.4230/LIPICS.ICALP.2025.10MaRDI QIDQ7346439zbMATH OpenFDO

Authors Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, Sumedha

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.10

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem
• A linear-time optimal broadcasting algorithm in stars of cliques
• A simplified NP-complete satisfiability problem
• A survey of gossiping and broadcasting in communication networks
• Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks
• Approximation Algorithms for Minimum-Time Broadcast
• Broadcast Networks of Bounded Degree
• Broadcasting in the butterfly network
• Broadcasting on cactus graphs
• Centdian computation in cactus graphs
• Constant approximation for broadcasting in k-cycle graph
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 1375584 (Why is no real title available?)
• Improved approximation for broadcasting in k-path graphs
• Information Dissemination in Trees
• Linear Algorithm for Broadcasting in Unicyclic Graphs
• Message Multicasting in Heterogeneous Networks
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• On broadcasting in unicyclic graphs
• Parameterized complexity of broadcasting in graphs
• Polynomial-time algorithms for minimum-time broadcast in trees
• Sublogarithmic approximation for telephone multicast
• Tight Bounds on Mimimum Broadcast Networks

This page was built for publication: On the complexity of telephone broadcasting from cacti to bounded pathwidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346439)