| dc.contributor.author | Fomin, Fedor | |
| dc.contributor.author | Pierre, Fraigniaud | |
| dc.contributor.author | Golovach, Petr | |
| dc.date.accessioned | 2024-08-14T13:21:04Z | |
| dc.date.available | 2024-08-14T13:21:04Z | |
| dc.date.created | 2024-01-17T14:13:56Z | |
| dc.date.issued | 2023 | |
| dc.identifier.issn | 0302-9743 | |
| dc.identifier.uri | https://hdl.handle.net/11250/3146312 | |
| dc.description | Under embargo until: 2024-09-23 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.language.iso | eng | en_US |
| dc.publisher | Springer | en_US |
| dc.title | Parameterized Complexity of Broadcasting in Graphs | en_US |
| dc.type | Journal article | en_US |
| dc.type | Peer reviewed | en_US |
| dc.description.version | acceptedVersion | en_US |
| dc.rights.holder | Copyright 2023 The Author(s) | en_US |
| cristin.ispublished | true | |
| cristin.fulltext | postprint | |
| cristin.qualitycode | 1 | |
| dc.identifier.doi | https://doi.org/10.1007/978-3-031-43380-1_24 | |
| dc.identifier.cristin | 2228740 | |
| dc.source.journal | Lecture Notes in Computer Science (LNCS) | en_US |
| dc.source.pagenumber | 34–347 | en_US |
| dc.relation.project | Norges forskningsråd: 314528 | en_US |
| dc.identifier.citation | Lecture Notes in Computer Science (LNCS). 2023, 14093, 34–347. | en_US |
| dc.source.volume | 14093 | en_US |
