A single exponential-time FPT algorithm for cactus contraction
| dc.contributor.author | Krithika, R. | en_US |
| dc.contributor.author | Misra , Pranabendu | en_US |
| dc.contributor.author | TALE, PRAFULLKUMAR | en_US |
| dc.contributor.department | Dept. of Mathematics | en_US |
| dc.date.accessioned | 2023-04-19T06:48:09Z | |
| dc.date.available | 2023-04-19T06:48:09Z | |
| dc.date.issued | 2023-04 | en_US |
| dc.description.abstract | For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F-CONTRACTION in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F-CONTRACTION where F is the set of all cactus graphs and show that we can solve it in 2O(k) center dot |V(G)|O(1) time. | en_US |
| dc.identifier.citation | Theoretical Computer Science, 954, 113803. | en_US |
| dc.identifier.issn | 0304-3975 | en_US |
| dc.identifier.issn | 1879-2294 | en_US |
| dc.identifier.sourcetitle | Theoretical Computer Science | en_US |
| dc.identifier.uri | https://doi.org/10.1016/j.tcs.2023.113803 | |
| dc.identifier.uri | http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7715 | |
| dc.language.iso | en | en_US |
| dc.publication.originofpublisher | Foreign | en_US |
| dc.publisher | Elsevier B.V. | en_US |
| dc.subject | Fixed parameter tractable algorithms | en_US |
| dc.subject | Graph contraction | en_US |
| dc.subject | Cactus graphs | en_US |
| dc.subject | 2023-APR-WEEK1 | en_US |
| dc.subject | TOC-APR-2023 | en_US |
| dc.subject | 2023 | en_US |
| dc.title | A single exponential-time FPT algorithm for cactus contraction | en_US |
| dc.type | Article | en_US |