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

DOI10.1016/j.tcs.2022.01.031OpenAlexW4207030071MaRDI QIDQ2078619

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

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

knotFPTW[1-hard]ETHdeadlock resolution

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Revisiting the complexity of and/or graph solution
• Monadic second-order evaluations on tree-decomposable graphs
• Time efficient deadlock resolution algorithms
• Which problems have strongly exponential complexity?
• And/or-convexity: a graph convexity based on processes and deadlock models
• Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
• A two-level distributed detection algorithm of AND/OR deadlocks
• Linear time solvable optimization problems on graphs of bounded clique-width
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• Deletion graph problems based on deadlock resolution
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• On Minimum Cost Recovery from System Deadlock
• A fixed-parameter algorithm for the directed feedback vertex set problem
• The Complexity of Satisfiability of Small Depth Circuits
• Graph minors. II. Algorithmic aspects of tree-width
• A Distributed Graph Algorithm: Knot Detection
• Kernelization Lower Bounds Through Colors and IDs
• Approximating rank-width and clique-width quickly
• Reducibility among Combinatorial Problems
• Parameterized Algorithms

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