On kernelization and approximation for the vector connectivity problem

DOI10.1007/s00453-016-0231-yzbMath1372.68138arXiv1410.8819MaRDI 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

approximation; graph algorithms; NP-hard problem; parameterized complexity; kernelization; separators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B80: Discrete location and assignment

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C40: Connectivity

Uses Software

• Stony Brook