On the computational complexity of length- and neighborhood-constrained path problems

DOI10.1016/j.ipl.2019.105913zbMath1478.68251arXiv1808.02359OpenAlexW2999089703WikidataQ126403679 ScholiaQ126403679MaRDI QIDQ2294439

Till Fluschnik, Max-Jonathan Luckow

Publication date: 11 February 2020

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityfixed-parameter tractabilityproblem kernelizationsecludedness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ Finding \(k\)-secluded trees faster

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On problems without polynomial kernels
• Which problems have strongly exponential complexity?
• Secluded connectivity problems
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Parameterized complexity of secluded connectivity problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms

This page was built for publication: On the computational complexity of length- and neighborhood-constrained path problems