\textsc{Telephone Broadcast} on graphs of treewidth two

DOI10.1016/J.TCS.2025.115282MaRDI QIDQ6975892zbMATH OpenFDO

Authors Prafullkumar Tale

Publication date 2 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115282

zbMATH Keywords

double exponential lower boundETH-based lower boundNP-hardnesstelephone broadcasting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A polynomial algorithm for the min-cut linear arrangement of trees
• A survey of gossiping and broadcasting in communication networks
• Approximation Algorithms for Minimum-Time Broadcast
• Automata, Languages and Programming
• Broadcasting in split graphs
• Broadcasting on cactus graphs
• Complexity results for minimum sum edge coloring
• Constant approximation for broadcasting in k-cycle graph
• Grundy Coloring and friends, half-graphs, bicliques
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 857072 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Information Dissemination in Trees
• Known algorithms for edge clique cover are probably optimal
• Message Multicasting in Heterogeneous Networks
• Methods and problems of communication in usual networks
• Min Cut is NP-complete for edge weighted trees
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• On broadcasting in unicyclic graphs
• On the parameterized complexity of biclique cover and partition
• Parameterized algorithms
• Parameterized complexity of broadcasting in graphs
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Sublogarithmic approximation for telephone multicast
• The complexity of restricted spanning tree problems
• The minimum broadcast time problem for several processor networks

This page was built for publication: \textsc{Telephone Broadcast} on graphs of treewidth two

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