Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Bevern, R.V. and Fluschnik, T. and Mertzios, G.B. and Molter, H. and Sorge, M. and Suchý, O. (2018) 'The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs.', Discrete optimization., 30 . pp. 20-50.

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.

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
File format - PDF
(774Kb)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (Revised version)
(775Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.disopt.2018.05.002
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:21 May 2018
Date deposited:22 May 2018
Date of first online publication:16 August 2018
Date first made open access:16 August 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar