On kernelization and approximation for the vector connectivity problem

DOI10.4230/LIPICS.IPEC.2015.377MaRDI QIDQ5363790zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Manuel Sorge

Publication date 29 September 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.377

zbMATH Keywords

approximationparameterized complexitykernelization

Mathematics Subject Classification ID

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

Recommendations

• On kernelization and approximation for the vector connectivity problem
• On the complexity of the vector connectivity problem
• Vector connectivity in graphs
• Vector connectivity in graphs
• Approximating \(k\)-generalized connectivity via collapsing HSTs

Cited in

(7)

• Designing FPT algorithms for cut problems using randomized contractions
• scientific article; zbMATH DE number 6857816 (Why is no real title available?)
• Vector connectivity in graphs
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• scientific article; zbMATH DE number 7720021 (Why is no real title available?)
• On the complexity of the vector connectivity problem
• On kernelization and approximation for the vector connectivity problem

This page was built for publication: On kernelization and approximation for the vector connectivity problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363790)