Parameterized Complexity of Broadcasting in Graphs
Journal article, Peer reviewed
Accepted version
View/ Open
Date
2023Metadata
Show full item recordCollections
- Department of Informatics [970]
- Registrations from Cristin [10186]
Original version
Lecture Notes in Computer Science (LNCS). 2023, 14093, 34–347. https://doi.org/10.1007/978-3-031-43380-1_24Abstract
The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to be NP-hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by , where t is the input deadline for the broadcast protocol to complete.
Description
Under embargo until: 2024-09-23