Finding connected secluded subgraphs

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

Authors: Petr A. Golovach, Pinar Heggernes, Pedro Montealegre, 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
• 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
• Finding secluded places of special interest in graphs

Cited In (9)

• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• Parameterized complexity of connected induced subgraph problems
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Finding secluded places of special interest in graphs
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• Finding connected secluded subgraphs
• 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)