On kernelization and approximation for the vector connectivity problem

DOI10.1007/s00453-016-0231-yzbMath1372.68138arXiv1410.8819OpenAlexW1526906366MaRDI QIDQ2408198

Stefan Kratsch, Manuel Sorge

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximationgraph algorithmsNP-hard problemparameterized complexitykernelizationseparators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Uses Software

• Stony Brook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A parameterized view on matroid optimization problems
• A completeness theory for polynomial (Turing) kernelization
• On the complexity of the vector connectivity problem
• Parametrized complexity theory.
• Applications of Menger's graph theorem
• Finding small separators in linear time via treewidth reduction
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Vector Connectivity in Graphs
• On Dominating Sets and Independent Sets of Graphs
• Kernelization Lower Bounds Through Colors and IDs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Kernelization Lower Bounds by Cross-Composition
• Representative Sets and Irrelevant Vertices
• (Meta) Kernelization
• On Kernelization and Approximation for the Vector Connectivity Problem
• Bidimensionality and Geometric Graphs
• Parameterized Algorithms