Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

DOI10.1016/j.tcs.2012.05.031zbMath1247.68110OpenAlexW2129208193MaRDI QIDQ714786

Peter Damaschke, Leonid Molokov

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.031

zbMATH Keywords

error correctionvertex coverparameterized complexityhitting setgraph editingproblem kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Circulant graphs and GCD and LCM of subsets

Cites Work

• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Vertex and edge covers with clustering properties: Complexity and algorithms
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• Parameterized complexity of Vertex Cover variants
• An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
• Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover
• Nondeterminism within $P^ * $
• Improved Upper Bounds for Partial Vertex Cover
• Parameterized Algorithms for Generalized Domination

This page was built for publication: Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover