Výsledky vyhledávání - "Bart M.P. Jansen"

A Turing kernelization dichotomy for structural parameterizations of F-Minor-Free Deletion

Publikováno v: Journal of Computer and System Sciences, 119, 164-182. Academic Press Inc.

For a fixed finite family of graphs F, the F-MINOR-FREE DELETION problem takes as input a graph G and integer ℓ and asks whether a size-ℓ vertex set X exists such that G−X is F-minor-free. {K2}-MINOR-FREE DELETION and {K3}-MINOR-FREE DELETION e

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::341fc9e6c64418ae7cb722aa058655eb
https://research.tue.nl/nl/publications/d449b5ab-4d10-401e-a6c5-b5a2193ec155

Zobrazit plný text záznamu

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms

Autor: Carl Einarson, Gregory Gutin, Bart M.P. Jansen, Diptapriyo Majumdar, Magnus Wahlström

We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$-Edge-Connected and $p$-Vertex-Connected VC problem (where $p \geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do no

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe69d19439ddaf93174d4c22e7f2b26c

Zobrazit plný text záznamu

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

Autor: Lars Jaffke, Bart M.P. Jansen

The $q$-Coloring problem asks whether the vertices of a graph can be properly colored with $q$ colors. Lokshtanov et al. [SODA 2011] showed that $q$-Coloring on graphs with a feedback vertex set of size $k$ cannot be solved in time $\mathcal{O}^*((q-

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::63c07f9cc7ef181f21539b3b7b6d220b
http://arxiv.org/abs/1701.06985

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání