Broadcasting in Stars of Cliques and Path-Connected Cliques
Broadcasting is a fundamental information dissemination problem in a connected network where one node, referred to as the originator, must distribute a message to all other nodes through a series of calls along the network’s links. Once informed, nodes assist the originator by forwarding the message...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/2/76 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850080259015180288 |
|---|---|
| author | Akash Ambashankar Hovhannes A. Harutyunyan |
| author_facet | Akash Ambashankar Hovhannes A. Harutyunyan |
| author_sort | Akash Ambashankar |
| collection | DOAJ |
| description | Broadcasting is a fundamental information dissemination problem in a connected network where one node, referred to as the originator, must distribute a message to all other nodes through a series of calls along the network’s links. Once informed, nodes assist the originator by forwarding the message to their neighbors. Determining the broadcast time for a node in an arbitrary network is NP-complete. While polynomial-time algorithms exist for specific network topologies, the problem remains open for many others. In this paper, we focus on addressing the broadcasting problem in network topologies represented by specialized clique-based structures. Specifically, we investigate the windmill graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>W</mi><msub><mi>d</mi><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msub></mrow></semantics></math></inline-formula>, which consists of <i>k</i> cliques of size <i>l</i> connected to a universal node, and extend our study to the star of cliques, a generalization of the windmill graph with cliques of arbitrary sizes. Our primary objective is to propose an efficient algorithm for determining the broadcast time of any node in an arbitrary star of cliques and to rigorously prove its optimality. Additionally, we broaden the scope by examining the broadcasting problem in path-connected cliques, a topology featuring <i>k</i> cliques of varying sizes sequentially connected along a path. For this structure, we develop a computationally efficient algorithm that leverages clique sizes and adjacency to optimize broadcast strategies, with broader implications for understanding communication in block graphs. |
| format | Article |
| id | doaj-art-1a4352fb50ec44f8a43031ca88445d42 |
| institution | DOAJ |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-1a4352fb50ec44f8a43031ca88445d422025-08-20T02:44:59ZengMDPI AGAlgorithms1999-48932025-02-011827610.3390/a18020076Broadcasting in Stars of Cliques and Path-Connected CliquesAkash Ambashankar0Hovhannes A. Harutyunyan1Department of Computer Science and Software Engineering, Concordia University, Montreal, QC H3G 1M8, CanadaDepartment of Computer Science and Software Engineering, Concordia University, Montreal, QC H3G 1M8, CanadaBroadcasting is a fundamental information dissemination problem in a connected network where one node, referred to as the originator, must distribute a message to all other nodes through a series of calls along the network’s links. Once informed, nodes assist the originator by forwarding the message to their neighbors. Determining the broadcast time for a node in an arbitrary network is NP-complete. While polynomial-time algorithms exist for specific network topologies, the problem remains open for many others. In this paper, we focus on addressing the broadcasting problem in network topologies represented by specialized clique-based structures. Specifically, we investigate the windmill graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>W</mi><msub><mi>d</mi><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msub></mrow></semantics></math></inline-formula>, which consists of <i>k</i> cliques of size <i>l</i> connected to a universal node, and extend our study to the star of cliques, a generalization of the windmill graph with cliques of arbitrary sizes. Our primary objective is to propose an efficient algorithm for determining the broadcast time of any node in an arbitrary star of cliques and to rigorously prove its optimality. Additionally, we broaden the scope by examining the broadcasting problem in path-connected cliques, a topology featuring <i>k</i> cliques of varying sizes sequentially connected along a path. For this structure, we develop a computationally efficient algorithm that leverages clique sizes and adjacency to optimize broadcast strategies, with broader implications for understanding communication in block graphs.https://www.mdpi.com/1999-4893/18/2/76broadcastingalgorithmstar of cliquespath-connected cliqueswindmill graphs |
| spellingShingle | Akash Ambashankar Hovhannes A. Harutyunyan Broadcasting in Stars of Cliques and Path-Connected Cliques Algorithms broadcasting algorithm star of cliques path-connected cliques windmill graphs |
| title | Broadcasting in Stars of Cliques and Path-Connected Cliques |
| title_full | Broadcasting in Stars of Cliques and Path-Connected Cliques |
| title_fullStr | Broadcasting in Stars of Cliques and Path-Connected Cliques |
| title_full_unstemmed | Broadcasting in Stars of Cliques and Path-Connected Cliques |
| title_short | Broadcasting in Stars of Cliques and Path-Connected Cliques |
| title_sort | broadcasting in stars of cliques and path connected cliques |
| topic | broadcasting algorithm star of cliques path-connected cliques windmill graphs |
| url | https://www.mdpi.com/1999-4893/18/2/76 |
| work_keys_str_mv | AT akashambashankar broadcastinginstarsofcliquesandpathconnectedcliques AT hovhannesaharutyunyan broadcastinginstarsofcliquesandpathconnectedcliques |