On structural parameterizations of the bounded-degree vertex deletion problem

DOI10.1007/S00453-020-00758-8zbMATH Open1487.68178OpenAlexW3065763739MaRDI QIDQ2223699FDOQ2223699

Authors: Robert Ganian, Fabian Klute, Sebastian Ordyniak 

Publication date: 1 February 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00758-8

Recommendations

• On structural parameterizations of the bounded-degree vertex deletion problem
• On bounded-degree vertex deletion parameterized by treewidth
• A parameterized algorithm for bounded-degree vertex deletion
• Approximating bounded degree deletion via matroid matching
• Approximating partially bounded degree deletion on directed graphs

zbMATH Keywords

parameterized algorithmsfeedback vertex setbounded-degree vertex deletiontreecut width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Integer Programming with a Fixed Number of Variables
• A linear kernel for co-path/cycle packing
• Minkowski's Convex Body Theorem and Integer Programming
• Title not available (Why is that?)
• Parameterized algorithms
• Title not available (Why is that?)
• A generalization of Nemhauser and Trotter's local optimization theorem
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Kernelization Lower Bounds by Cross-Composition
• Backdoors into heterogeneous classes of SAT and CSP
• Treewidth. Computations and approximations
• A graph‐theoretic generalization of the clique concept
• Sparsity. Graphs, structures, and algorithms
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On bounded-degree vertex deletion parameterized by treewidth
• An application of simultaneous diophantine approximation in combinatorial optimization
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• Kernelization using structural parameters on sparse graph classes
• Graph Layout Problems Parameterized by Vertex Cover
• The multidimensional 0-1 knapsack problem: an overview.
• The structure of graphs not admitting a fixed immersion
• Immersions in highly edge connected graphs
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Title not available (Why is that?)
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Isolation concepts for efficiently enumerating dense subgraphs
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Parameterized complexity of candidate control in elections and related digraph problems
• Reduction algorithms for graphs of small treewidth
• A complete parameterized complexity analysis of bounded planning
• On making a distinguished vertex of minimum degree by vertex deletion
• Solving problems on graphs of high rank-width
• Meta-kernelization using Well-structured Modulators
• Title not available (Why is that?)
• On structural parameterizations of the bounded-degree vertex deletion problem
• Meta-kernelization with structural parameters
• Algorithmic applications of tree-cut width
• Backdoors to planning
• The power of cut-based parameters for computing edge disjoint paths
• SAT-encodings for treecut width and treedepth

Cited In (22)

• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Algorithmic applications of tree-cut width
• Slim tree-cut width
• Approximating bounded degree deletion via matroid matching
• Parameterized intractability of defensive alliance problem
• On structural parameterizations of the bounded-degree vertex deletion problem
• Approximating partially bounded degree deletion on directed graphs
• Approximating partially bounded degree deletion on directed graphs
• On bounded-degree vertex deletion parameterized by treewidth
• Hedonic diversity games: a complexity picture with more than two colors
• Group activity selection with few agent types
• Extended MSO model checking via small vertex integrity
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Structural parameterizations for two bounded degree problems revisited
• On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
• On structural parameterizations of the offensive alliance problem
• A parameterized algorithm for bounded-degree vertex deletion
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

This page was built for publication: On structural parameterizations of the bounded-degree vertex deletion problem

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