R.V. Bevern
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.
Authors
T. Fluschnik
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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
Accepted Journal Article (Revised version)
(794 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
Revised version © 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/
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search