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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA17-20065S" target="_blank" >GA17-20065S: Tight Parameterized Results for Directed Connectivity Problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)