Parameterized complexity of secluded connectivity problems
From MaRDI portal
Publication:2408560
DOI10.1007/s00224-016-9717-xzbMath1378.68075arXiv1502.03989OpenAlexW1532687347WikidataQ60488378 ScholiaQ60488378MaRDI QIDQ2408560
Nikolay Karpov, Fedor V. Fomin, Alexander S. Kulikov, Petr A. Golovach
Publication date: 12 October 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.03989
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (7)
Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Finding \(k\)-secluded trees faster ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ On the computational complexity of length- and neighborhood-constrained path problems ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- VC-dimension of perimeter visibility domains
- Exact exponential algorithms.
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- On the parameterized complexity of multiple-interval graph problems
- On problems without polynomial kernels
- Secluded connectivity problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Treewidth computation and extremal combinatorics
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Fourier meets M\"{o}bius: fast subset convolution
- Color-coding
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- Parameterized Complexity of Secluded Connectivity Problems
- Secluded Path via Shortest Path
- Parameterized Algorithms
- The steiner problem in graphs
This page was built for publication: Parameterized complexity of secluded connectivity problems
