Cover Image

On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aminian, Aida, Kamali, Shahin, Seyed-Javadi, Seyed-Mohammad, Sumedha
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Hardness and Approximation of Broadcasting in Structured Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

On Approximating Cutwidth and Pathwidth
by: Bansal, Nikhil, et al.
Published: (2023)

Online Bin Covering with Frequency Predictions
by: Berg, Magnus, et al.
Published: (2024)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
by: Casel, Katrin, et al.
Published: (2019)

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
by: Nakamura, Kengo, et al.
Published: (2026)

Robust Learning-Augmented Dictionaries
by: Zeynali, Ali, et al.
Published: (2024)

Green Bin Packing
by: Bibbens, Jackson, et al.
Published: (2025)

The Primal Pathwidth SETH
by: Lampis, Michael
Published: (2024)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
by: Tale, Prafullkumar
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

Online Computation with Untrusted Advice
by: Angelopoulos, Spyros, et al.
Published: (2019)

Optimizing Distances for Multi-Broadcast in Temporal Graphs
by: Carnevale, Daniele, et al.
Published: (2026)

Reconfiguration of Multisets with Applications to Bin Packing
by: Kam, Jeffrey, et al.
Published: (2024)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
by: Kaznatcheev, Artem, et al.
Published: (2024)

Time Fairness in Online Knapsack Problems
by: Lechowicz, Adam, et al.
Published: (2023)

Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
by: Wirth, Leoni Carla, et al.
Published: (2025)

Online Interval Scheduling with Predictions
by: Boyar, Joan, et al.
Published: (2023)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty
by: Tsou, Cheng-Hsiao, et al.
Published: (2024)

Minimizing the Size of the Uncertainty Regions for Centers of Moving Entities
by: Evans, William, et al.
Published: (2023)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
by: Beisegel, Jesse, et al.
Published: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
by: Huiberts, Sophie, et al.
Published: (2022)

Distributed Model Checking on Graphs of Bounded Treedepth
by: Fomin, Fedor V., et al.
Published: (2024)

The Telephone $k$-Multicast Problem
by: Hathcock, Daniel, et al.
Published: (2024)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
by: Manea, Florin, et al.
Published: (2024)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

Source-Oblivious Broadcast
by: Fraigniaud, Pierre, et al.
Published: (2025)

The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
by: Komoto, Kenta, et al.
Published: (2026)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)