Parameterized algorithms and data reduction for the short secluded s‐t‐path problem

DOI10.1002/net.21904arXiv1806.09540OpenAlexW3103988870MaRDI QIDQ6068532

Till Fluschnik, O. Yu. Tsidulko, René van Bevern

Publication date: 13 November 2023

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

treewidthNP-hard problemfixed-parameter tractabilitysubexponential timeproblem kernelizationkernelization lower bounds

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) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Finding \(k\)-secluded trees faster

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• Polynomial kernels for weighted problems
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Fundamentals of parameterized complexity
• Parameterized complexity of \(k\)-Chinese postman problem
• Lower bounds on kernelization
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Linearity of grid minors in treewidth with applications through bidimensionality
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• An application of simultaneous diophantine approximation in combinatorial optimization
• Which problems have strongly exponential complexity?
• Secluded connectivity problems
• Parameterized approximation via fidelity preserving transformations
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• A new view on rural postman based on Eulerian extension and matching
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• A completeness theory for polynomial (Turing) kernelization
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Parameterized complexity of secluded connectivity problems
• The parameterized approximability of TSP with deadlines
• Parametrized complexity theory.
• Über eine Eigenschaft der ebenen Komplexe
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• From Few Components to an Eulerian Graph by Adding Arcs
• The Minor Crossing Number
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Compression via Matroids
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• Efficient Algorithms for Eulerian Extension and Rural Postman
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• Parameterized Algorithms
• Parameterized Traveling Salesman Problem: Beating the Average

This page was built for publication: Parameterized algorithms and data reduction for the short secluded s‐t‐path problem