A Parameterized Algorithm for Bounded-Degree Vertex Deletion

DOI10.1007/978-3-319-42634-1_7zbMath1476.68219arXiv1601.00163OpenAlexW3102537597MaRDI QIDQ2817850

Mingyu Xiao

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsparameterized algorithmsbounded-degree vertex deletionhitting set

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Unnamed Item ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Cites Work

• On a generalization of Nemhauser and Trotter's local optimization theorem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Exact exponential algorithms.
• A generalization of Nemhauser and Trotter's local optimization theorem
• Improved upper bounds for vertex cover
• On bounded-degree vertex deletion parameterized by treewidth
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• A faster FPT algorithm for 3-path vertex cover
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Every Property of Hyperfinite Graphs Is Testable
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Parameterized algorithmics for d-H<scp>itting</scp> S<scp>et</scp>
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• A Linear Kernel for Co-Path/Cycle Packing
• A graph‐theoretic generalization of the clique concept

This page was built for publication: A Parameterized Algorithm for Bounded-Degree Vertex Deletion