Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874230 | Information Processing Letters | 2018 | 12 Pages |
Abstract
Recent papers investigated the maximum infection times tP3(G), tgd(G) and tmo(G) of the P3 convexity, geodesic convexity and monophonic convexity, respectively. In [4] and [8], it was proved that deciding whether tgd(G)â¥2 or tmo(G)â¥2 are NP-Complete problems even for bipartite graphs. In [17], it was proved that, in bipartite graphs, deciding whether tP3(G)â¥k is polynomial time solvable for kâ¤4, but is NP-Complete for kâ¥5. In this paper, we prove that the P3 infection time problem is fixed parameter tractable parameterized by treewidth + k, but is W[1]-hard when parameterized only by the treewidth.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Thiago Marcilon, Rudini Sampaio,