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 Library locked




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


cfvs_jv.pdf (198.84 KB)

Journal

Journal Title*:

Journal of Combinatorial Optimization

Journal's URL:

http://www.springerlink.com/content/1382-6905/24/2/

Download URL
for the article:

http://www.springerlink.com/content/g81624011r5u6411/fulltext.pdf

Language:

English

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, Abstract, ©

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},
ADDRESS = {New York, NY},
MONTH = {August},
ISBN = {1382-6905},
DOI = {10.1007/s10878-011-9394-2},
}


Entry last modified by Anja Becker, 07/08/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
04/21/2012 07:13:51 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Geevarghese Philip
Geevarghese Philip
Edit Dates
08.02.2013 12:30:40
08.02.2013 12:30:29
12/08/2012 04:59:40 AM
04/21/2012 07:13:51 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
cfvs_jv.pdf