The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F18%3A00328401" target="_blank" >RIV/68407700:21240/18:00328401 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S1572528617301160?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S1572528617301160?via%3Dihub</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disopt.2018.05.002" target="_blank" >10.1016/j.disopt.2018.05.002</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

Popis výsledku v původním jazyce

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

Název v anglickém jazyce

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

Popis výsledku anglicky

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

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/GA17-20065S" target="_blank" >GA17-20065S: Těsné parametrizované výsledky pro problémy orientované souvislosti</a><br>

Návaznosti

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

Rok uplatnění

2018

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

Discrete Optimization

ISSN

1572-5286

e-ISSN

1873-636X

Svazek periodika

30

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

31

Strana od-do

20-50

Kód UT WoS článku

000451495000002

EID výsledku v databázi Scopus

2-s2.0-85048565401