Finding connected secluded subgraphs

DOI10.4230/LIPICS.IPEC.2017.18zbMATH Open1443.68129arXiv1710.10979MaRDI QIDQ5111877FDOQ5111877

Pinar Heggernes, Pedro Montealegre, Petr A. Golovach, Paloma T. Lima

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1710.10979

Recommendations

• Finding connected secluded subgraphs
• Parameterized complexity of finding connected induced subgraphs
• Parameterized complexity of connected induced subgraph problems
• Finding secluded places of special interest in graphs
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

zbMATH Keywords

parameterized complexityforbidden subgraphssecluded subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• The node-deletion problem for hereditary properties is NP-complete
• Parameterized Algorithms
• Parameterized graph separation problems
• On limited nondeterminism and the complexity of the V-C dimension
• Isolation concepts for efficiently enumerating dense subgraphs
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Secluded connectivity problems
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Isolation concepts for clique enumeration: comparison and computational experiments
• Enumeration of isolated cliques and pseudo-cliques
• Secluded Path via Shortest Path
• Parameterized complexity of secluded connectivity problems
• Title not available (Why is that?)

Cited In (4)

• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• On the computational complexity of length- and neighborhood-constrained path problems
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem

This page was built for publication: Finding connected secluded subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111877)