Skip to main content

Research Repository

Advanced Search

Finding secluded places of special interest in graphs

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

Finding secluded places of special interest in graphs Thumbnail


Authors

R.V. Bevern

T. Fluschnik

H. Molter

M. Sorge

O. Suchý



Contributors

Jiong Guo
Editor

Danny Hermelin
Editor

Abstract

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the “exposure” of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

Citation

Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2017). Finding secluded places of special interest in graphs. In J. Guo, & D. Hermelin (Eds.), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) : August 24-26, 2016, Aarhus, Denmark (5:1-5:16). https://doi.org/10.4230/lipics.ipec.2016.5

Conference Name 11th International Symposium on Parameterized and Exact Computation (IPEC)
Conference Location Aarhus, Denmark
Start Date Aug 24, 2016
End Date Aug 26, 2016
Acceptance Date Jul 24, 2016
Online Publication Date Jan 31, 2017
Publication Date Jan 31, 2017
Deposit Date Sep 1, 2016
Publicly Available Date Mar 29, 2024
Pages 5:1-5:16
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 63
Series ISSN 1868-8969
Book Title 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) : August 24-26, 2016, Aarhus, Denmark.
DOI https://doi.org/10.4230/lipics.ipec.2016.5
Public URL https://durham-repository.worktribe.com/output/1151285
Publisher URL http://drops.dagstuhl.de/opus/volltexte/2017/6938

Files






You might also like



Downloadable Citations