Finding connected secluded subgraphs

DOI10.1016/j.jcss.2020.05.006zbMath1443.68130OpenAlexW3026258808MaRDI QIDQ2186823

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

Publication date: 9 June 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8562/

zbMATH Keywords

forbidden subgraphsparameterized complexitysecluded subgraph

Mathematics Subject Classification ID

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

Related Items

Finding \(k\)-secluded trees faster, Finding \(k\)-secluded trees faster

Cites Work

• Fundamentals of parameterized complexity
• Parameterized graph separation problems
• Isolation concepts for efficiently enumerating dense subgraphs
• On problems without polynomial kernels
• Isolation concepts for clique enumeration: comparison and computational experiments
• The node-deletion problem for hereditary properties is NP-complete
• Modular decomposition and transitive orientation
• Secluded connectivity problems
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• On limited nondeterminism and the complexity of the V-C dimension
• On the computational complexity of length- and neighborhood-constrained path problems
• Treewidth computation and extremal combinatorics
• Parameterized complexity of secluded connectivity problems
• Enumeration of isolated cliques and pseudo-cliques
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Minimum Bisection Is Fixed-Parameter Tractable
• Reducing CMSO model checking to highly connected graphs
• Secluded Path via Shortest Path
• Parameterized Algorithms
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem