Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7715| Title: | A single exponential-time FPT algorithm for cactus contraction |
| Authors: | Krithika, R. Misra , Pranabendu TALE, PRAFULLKUMAR Dept. of Mathematics |
| Keywords: | Fixed parameter tractable algorithms Graph contraction Cactus graphs 2023-APR-WEEK1 TOC-APR-2023 2023 |
| Issue Date: | Apr-2023 |
| Publisher: | Elsevier B.V. |
| Citation: | Theoretical Computer Science, 954, 113803. |
| 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. |
| URI: | https://doi.org/10.1016/j.tcs.2023.113803 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7715 |
| ISSN: | 0304-3975 1879-2294 |
| Appears in Collections: | JOURNAL ARTICLES |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.