About: An FPT algorithm for Tree Deletion Set

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: An FPT algorithm for Tree Deletion Set Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://jgaa.info/getPaper?id=308
Description	We give a~$5^k n^{O(1)}$ time fixed-parameter algorithm for determining whether a given undirected graph on~$n$ vertices has a subset of at most~$k$ vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set. We give a~$5^k n^{O(1)}$ time fixed-parameter algorithm for determining whether a given undirected graph on~$n$ vertices has a subset of at most~$k$ vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set. (en)
Title	An FPT algorithm for Tree Deletion Set An FPT algorithm for Tree Deletion Set (en)
skos:prefLabel	An FPT algorithm for Tree Deletion Set An FPT algorithm for Tree Deletion Set (en)
skos:notation	RIV/68407700:21240/13:00209343!RIV14-MSM-21240___
http://linked.open...avai/predkladatel	Fakulta informačních technologií
http://linked.open...avai/riv/aktivita	I
http://linked.open...avai/riv/aktivity	I
http://linked.open...iv/cisloPeriodika	6
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Suchý, Ondřej
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta informačních technologií
http://linked.open...dnocenehoVysledku	60363
http://linked.open...ai/riv/idVysledku	RIV/68407700:21240/13:00209343
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Feedback Vertex Set; Tree; FPT Algorithms; Graph Connectivity; Parameterized Complexity (en)
http://linked.open.../riv/klicoveSlovo	FPT Algorithms Feedback Vertex Set Graph Connectivity Tree Parameterized Complexity
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[2B03E79AD72B]
http://linked.open...i/riv/nazevZdroje	Journal of Graph Algorithms and Applications
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	17
http://linked.open...iv/tvurceVysledku	Suchý, Ondřej Saurabh, S. Raman, V.
issn	1526-1719
number of pages	14 (xsd:int)
http://bibframe.org/vocab/doi	10.7155/jgaa.00308
http://localhost/t...ganizacniJednotka	21240

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software