FPT approximation and subexponential algorithms for covering few or many edges

DOI10.1016/j.ipl.2024.106471arXiv2308.15546OpenAlexW4390726254MaRDI QIDQ6195348

Petr A. Golovach, Fedor V. Fomin, Unnamed Author, Tomohiro Koana

Publication date: 13 March 2024

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsparameterized complexitypartial vertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implicit branching and parameterized partial cover problems
• Linearity of grid minors in treewidth with applications through bidimensionality
• Clustering and domination in perfect graphs
• Subexponential algorithms for partial cover problems
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Parameterized algorithms for graph partitioning problems
• Parameterized complexity of Vertex Cover variants
• Contraction Bidimensionality: The Accurate Picture
• Bidimensional Parameters and Local Treewidth
• Parameterized Algorithms
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

This page was built for publication: FPT approximation and subexponential algorithms for covering few or many edges