Finding connected secluded subgraphs

DOI10.4230/LIPICS.IPEC.2017.18MaRDI QIDQ5111877zbMATH OpenFDO

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

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)

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

Cites work

• Designing FPT algorithms for cut problems using randomized contractions
• Enumeration of isolated cliques and pseudo-cliques
• Finding secluded places of special interest in graphs
• Fundamentals of parameterized complexity
• Isolation concepts for clique enumeration: comparison and computational experiments
• Isolation concepts for efficiently enumerating dense subgraphs
• On limited nondeterminism and the complexity of the V-C dimension
• Parameterized algorithms
• Parameterized complexity of secluded connectivity problems
• Parameterized graph separation problems
• Secluded path via shortest path
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(9)

• Finding connected secluded subgraphs
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• On the computational complexity of length- and neighborhood-constrained path problems
• Finding secluded places of special interest in graphs
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Parameterized complexity of connected induced subgraph problems
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster

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)