On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

DOI10.1016/J.TCS.2022.01.031MaRDI QIDQ2078619zbMATH OpenOpenAlexFDO

Authors Alan Diêgo Aurélio Carneiro, Fábio Protti, Uéverton dos Santos Souza

Publication date 1 March 2022

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

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

zbMATH Keywords

deadlock resolutionETHFPTknotW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
• Deletion graph problems based on deadlock resolution
• Width Parameterizations for Knot-Free Vertex Deletion on Digraphs.
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• On structural parameterizations of the bounded-degree vertex deletion problem
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized complexity of vertex deletion into perfect graph classes

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Distributed Graph Algorithm: Knot Detection
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A two-level distributed detection algorithm of AND/OR deadlocks
• And/or-convexity: a graph convexity based on processes and deadlock models
• Approximating rank-width and clique-width quickly
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Deletion graph problems based on deadlock resolution
• Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
• Graph minors. II. Algorithmic aspects of tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory with applications
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Introduction to algorithms.
• Kernelization lower bounds through colors and IDs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monadic second-order evaluations on tree-decomposable graphs
• On Minimum Cost Recovery from System Deadlock
• Parameterized algorithms
• Reducibility among combinatorial problems
• Revisiting the complexity of and/or graph solution
• The complexity of satisfiability of small depth circuits
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Time efficient deadlock resolution algorithms
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• Which problems have strongly exponential complexity?

Cited in

(1)

• Deletion graph problems based on deadlock resolution

This page was built for publication: On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

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