Header menu link for other important links
X
An FPT algorithm for contraction to cactus
, P. Misra, P. Tale
Published in Springer Verlag
2018
Volume: 10976 LNCS
   
Pages: 341 - 352
Abstract
For a collection F of graphs, given a graph G and an integer k, the F -Contraction problem asks whether we can contract k edges in G to obtain a graph in F. F -Contraction is well studied and known to be C-complete for several classes F. Heggerners et al. [Algorithmica (2014)] were the first to explicitly study contraction problems in the realm of parameterized complexity. They presented FPT algorithms for Tree-Contraction and Path-Contraction. In this paper, we study contraction to a class larger than trees, namely, cactus graphs. We present an FPT algorithm for Cactus-Contraction that runs in (Formula Presented) time for some constant c. © 2018, Springer International Publishing AG, part of Springer Nature.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo