Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F17%3A00313779" target="_blank" >RIV/68407700:21240/17:00313779 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/article/10.1007%2Fs00453-016-0249-1" target="_blank" >https://link.springer.com/article/10.1007%2Fs00453-016-0249-1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-016-0249-1" target="_blank" >10.1007/s00453-016-0249-1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

Popis výsledku v původním jazyce

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals |T| is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs.

Název v anglickém jazyce

Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

Popis výsledku anglicky

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals |T| is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GP14-13017P" target="_blank" >GP14-13017P: Parametrizované algoritmy pro základní síťové problémy spojené se souvislostí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

79

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

22

Strana od-do

189-210

Kód UT WoS článku

000405908000009

EID výsledku v databázi Scopus

2-s2.0-84997693845