Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2018) | last year (2017) | two years ago (2016) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Misra, Neeldhara Philip, Geevarghese Raman, Venkatesh Saurabh, Saket Sikdar, Somnath dblp dblp dblp dblp dblp Not MPG Author(s): Misra, Neeldhara Raman, Venkatesh Saurabh, Saket Sikdar, Somnath
 BibTeX cite key*: MisraPhilipRamanSaurabhSikdar2012

 Title
 Title*: FPT Algorithms for Connected Feedback Vertex Set Attachment(s): cfvs_jv.pdf (198.84 KB)

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer.com Publisher's Address: New York, NY ISSN: 1382-6905

 Vol, No, pp, Date
 Volume*: 24 Number: 2 Publishing Date: August 2012 Pages*: 131-146 Number of VG Pages: Page Start: Page End: Sequence Number: DOI: 10.1007/s10878-011-9394-2

 Note: (LaTeX) Abstract: We study the recently introduced \textsc{Connected Feedback Vertex Set (CFVS)} problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical \textsc{Feedback Vertex Set} problem and is defined as follows: given a graph $G=(V,E)$ and an integer $k$, decide whether there exists $F\subseteq V$, $|F| \leq k$, such that $G[V \setminus F]$ is a forest and $G[F]$ is connected. We show that \textsc{Connected Feedback Vertex Set} can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph $H$ as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for \textsc{Group Steiner Tree}, a well studied variant of \textsc{Steiner Tree}. We find the algorithm for \textsc{Group Steiner Tree} of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems. URL for the Abstract: http://www.springerlink.com/content/g81624011r5u6411/abstract/ Categories, Keywords: Parameterized Algorithms, Connected Feedback Vertex Set, Group Steiner Tree HyperLinks / References / URLs: Copyright Message: Copyright Springer Netherlands 2011. Published in the Journal of Combinatorial Optimization, DOI: 10.1007/s10878-011-9394-2 . The final publication is available at www.springerlink.com : http://www.springerlink.com/content/g81624011r5u6411/ Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{MisraPhilipRamanSaurabhSikdar2012,
AUTHOR = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket and Sikdar, Somnath},
TITLE = {{FPT} Algorithms for Connected Feedback Vertex Set},
JOURNAL = {Journal of Combinatorial Optimization},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {2},
VOLUME = {24},
PAGES = {131--146},