On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
type: Item
instance of: scholarly article
title: On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
author: Alan Diêgo Aurélio Carneiro
author: Fábio Protti
author: Uéverton dos Santos Souza
published in: Theoretical Computer Science
publication date: 2022-03-01T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7482358
zbMATH Keywords: knot
zbMATH Keywords: deadlock resolution
zbMATH Keywords: FPT
zbMATH Keywords: W[1]-hard
zbMATH Keywords: ETH
MaRDI profile type: Publication
full work available at URL: j.tcs.2022.01.031
OpenAlex ID: W4207030071
cites work: A \(c^k n\) 5-approximation algorithm for treewidth
cites work: Q3097395
cites work: The Complexity of Satisfiability of Small Depth Circuits
cites work: Deletion graph problems based on deadlock resolution
cites work: Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
cites work: Deadlock resolution in wait-for graphs by vertex/arc deletion
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: Q3651735
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q3077955
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Parameterized Algorithms
cites work: Kernelization Lower Bounds Through Colors and IDs
cites work: Q4393480
cites work: Q4198056
cites work: Which problems have strongly exponential complexity?
cites work: Reducibility among Combinatorial Problems
cites work: On Minimum Cost Recovery from System Deadlock
cites work: And/or-convexity: a graph convexity based on processes and deadlock models
cites work: A Distributed Graph Algorithm: Knot Detection
cites work: Q5710169
cites work: Approximating rank-width and clique-width quickly
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: A two-level distributed detection algorithm of AND/OR deadlocks
cites work: Tractability, hardness, and kernelization lower bound for and/or graph solution
cites work: Revisiting the complexity of and/or graph solution
cites work: Time efficient deadlock resolution algorithms
DOI: 10.1016/J.TCS.2022.01.031
Recommended article: Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
Recommended article: Deletion graph problems based on deadlock resolution
Recommended article: Width Parameterizations for Knot-Free Vertex Deletion on Digraphs.
Recommended article: Deadlock resolution in wait-for graphs by vertex/arc deletion
Recommended article: On structural parameterizations of the bounded-degree vertex deletion problem
Recommended article: On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Recommended article: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Recommended article: Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
Recommended article: Parameterized complexity of vertex deletion into perfect graph classes
description: scientific article; zbMATH DE number 7482358