Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.26426 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913117837983744 |
|---|---|
| author | Bringolf, Jeffrey Ehresmann, Anne-Laure Harutyunyan, Hovhannes A. |
| author_facet | Bringolf, Jeffrey Ehresmann, Anne-Laure Harutyunyan, Hovhannes A. |
| contents | Broadcasting is an information dissemination primitive where a message originates at a node (called the originator) and is passed to all other nodes in the network. Broadcasting research is motivated by efficient network design and determining the broadcast times of standard network topologies. Verifying the broadcast time of a node $v$ in an arbitrary network $G$ is known to be NP-hard. Additionally, recent findings show that the broadcast time problem is NP-hard in several highly restricted subfamilies of cactus graphs. The most restrictive of these families is known as \emph{$k$-cycle graphs} or \emph{flower graphs} and is the focus of this paper. We present a simple $(1.5-ε)$-approximation algorithm for determining the broadcast time of networks modeled using $k$-cycle graphs, where $ε> 0$ depends on the structure of the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26426 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs Bringolf, Jeffrey Ehresmann, Anne-Laure Harutyunyan, Hovhannes A. Data Structures and Algorithms F.2 Broadcasting is an information dissemination primitive where a message originates at a node (called the originator) and is passed to all other nodes in the network. Broadcasting research is motivated by efficient network design and determining the broadcast times of standard network topologies. Verifying the broadcast time of a node $v$ in an arbitrary network $G$ is known to be NP-hard. Additionally, recent findings show that the broadcast time problem is NP-hard in several highly restricted subfamilies of cactus graphs. The most restrictive of these families is known as \emph{$k$-cycle graphs} or \emph{flower graphs} and is the focus of this paper. We present a simple $(1.5-ε)$-approximation algorithm for determining the broadcast time of networks modeled using $k$-cycle graphs, where $ε> 0$ depends on the structure of the graph. |
| title | A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs |
| topic | Data Structures and Algorithms F.2 |
| url | https://arxiv.org/abs/2509.26426 |