The P3 infection time is W[1]-hard parameterized by the treewidth
type: Item
instance of: scholarly article
title: The P3 infection time is W[1]-hard parameterized by the treewidth
zbMATH Open document ID: 1427.68127
author: Thiago Marcilon
author: Rudini M. Sampaio
published in: Information Processing Letters
publication date: 2018-03-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6850980
zbMATH Keywords: computational complexity
zbMATH Keywords: infection time
zbMATH Keywords: \(P_3\) convexity
zbMATH Keywords: fixed parameter tractability
zbMATH Keywords: treewidth
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.12.006
OpenAlex ID: W2780415142
cites work: Bootstrap percolation in living neural networks
cites work: The sharp threshold for bootstrap percolation in all dimensions
cites work: The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
cites work: The maximum infection time in the geodesic and monophonic convexities
cites work: On slowly percolating sets of minimal size in bootstrap percolation
cites work: Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
cites work: Inapproximability results related to monophonic convexity
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Complexity results related to monophonic convexity
cites work: Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
cites work: On the complexity of some colorful problems parameterized by treewidth
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Growth rates and explosions in sandpiles
cites work: On the complexity of \(k\)-SAT
cites work: Q4904144
cites work: The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
cites work: The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
cites work: Graph minors. III. Planar tree-width
cites work: Diffusion in Social Networks
cites work: Q3141898
DOI: 10.1016/J.IPL.2017.12.006
Recommended article: The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
Recommended article: The infection time of graphs
Recommended article: On the vertex cover \(P_3\) problem parameterized by treewidth
Recommended article: Fixed-Parameter Tractability of Treewidth and Pathwidth
Recommended article: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
Recommended article: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Recommended article: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Recommended article: Inapproximability of Treewidth and Related Problems
Recommended article: Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
description: scientific article; zbMATH DE number 6850980