Skip to main content

Research Repository

Advanced Search

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

Bevern, R.V.; Fluschnik, T.; Mertzios, G.B.; Molter, H.; Sorge, M.; Suchý, O.

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


Authors

R.V. Bevern

T. Fluschnik

H. Molter

M. Sorge

O. Suchý



Abstract

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.

Citation

Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2018). The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimization, 30, 20-50. https://doi.org/10.1016/j.disopt.2018.05.002

Journal Article Type Article
Acceptance Date May 21, 2018
Online Publication Date Aug 16, 2018
Publication Date Nov 1, 2018
Deposit Date May 22, 2018
Publicly Available Date Mar 28, 2024
Journal Discrete Optimization
Print ISSN 1572-5286
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 30
Pages 20-50
DOI https://doi.org/10.1016/j.disopt.2018.05.002
Related Public URLs https://arxiv.org/abs/1606.09000

Files






You might also like



Downloadable Citations