On the Parameterized Complexity of Cutting a Few Vertices from a Graph

DOI10.1007/978-3-642-40313-2_38zbMath1398.68231arXiv1304.6189OpenAlexW3098053688WikidataQ60488435 ScholiaQ60488435MaRDI QIDQ2849930

Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen

Publication date: 20 September 2013

Published in: Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Parameterized complexity of immunization in the threshold model ⋮ On critical node problems with vulnerable vertices ⋮ Finding \(k\)-secluded trees faster ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Finding \(k\)-secluded trees faster ⋮ A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Unbalanced graph cuts with minimum capacity ⋮ Multilevel Approaches for the Critical Node Problem ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization

This page was built for publication: On the Parameterized Complexity of Cutting a Few Vertices from a Graph