English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  FPT Algorithms for Connected Feedback Vertex Set

Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2010). FPT Algorithms for Connected Feedback Vertex Set. In M. S. Rahman, & S. Fujita (Eds.), WALCOM: Algorithms and Computation (pp. 269-280). Berlin: Springer. doi:10.1007/978-3-642-11440-3_25.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC05-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC06-6
Genre: Conference Paper
Latex : {FPT} Algorithms for Connected Feedback Vertex Set

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Misra, Neeldhara1, Author
Philip, Geevarghese1, Author           
Raman, Venkatesh1, Author
Saurabh, Saket1, Author
Sikdar, Somnath1, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: We study the recently introduced \textscConnected 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| ≤q 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.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-11440-3_25
BibTex Citekey: MisraPhilipRamanSaurabhSikdar2010
 Degree: -

Event

show
hide
Title: WALCOM 2010
Place of Event: Dhaka, Bangladesh
Start-/End Date: 2010-02-10 - 2010-02-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: WALCOM: Algorithms and Computation
  Abbreviation : WALCOM 2010
  Subtitle : 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings
Source Genre: Proceedings
 Creator(s):
Rahman, Md. Saidur1, Editor
Fujita, Satoshi1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 269 - 280 Identifier: ISBN: 978-3-642-11439-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 5942 Sequence Number: - Start / End Page: - Identifier: -